T1 动态逆序对

题目

【题目描述】

给出一个长度为n的排列a（1~n这n个数在数列中各出现1次）。每次交换两个数，求逆序对数%2的结果。

逆序对：对于两个数a[i],a[j](i<j)，若a[i]>a[j]，则(a[i],a[j])为1个逆序对。

【输入格式】

第一行一个正整数n。

接下来一行n个数，表示给出的排列a。

接下来一行一个正整数q。

接下来q行，每行两个正整数i,j，表示交换a[i]和a[j]。

【输出格式】

输出共q行，表示每次交换后的逆序对数%2的结果。

【输入样例】

4
1 2 3 4
2
1 2
1 2

【输出样例】

1
0

【数据规模】

对于60%的数据：n,q≤100；

对于80%的数据：n,q≤1000；

对于100%的数据：n,q≤100000。

解析

先求出初始序列的逆序对总数对2取余的结果。

每次交换a[i]与a[j](i<j)，对于a[k]的影响如下：

• 若k<i，a[k]依旧在a[i]与a[j]前面，所以a[k]与a[i]、a[j]产生的逆序对数不变；
• 若k>j，同上，逆序对数不变；
• 若i<k<j，如果a[i]<a[k]，则逆序对数+1，否则-1,；如果a[j]>a[k]，则逆序对数+1，否则-1，

而我们只需求出逆序对数对2取余的结果，可以发现，逆序对个数的奇偶性与k无关。

事实上，只需在每次交换位置时，令逆序对总数对2取余的结果^1即可（i=j时则不变）。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,q,a[100100],f[100100],temp;
void add(int x,int y)
{
    for(;x<=n;x+=(x&-x)) f[x]+=y;
}
int ask(int x)
{
    int ans=0;
    for(;x;x-=(x&-x)) ans+=f[x];
    return ans;
}
int main()
{
    //freopen("lyk.in","r",stdin);
    //freopen("lyk.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    q=read();
    for(int i=n;i>=1;i--)
    {
        temp+=ask(a[i]-1);
        add(a[i],1);
    }
    temp&=1;
    for(int i=1;i<=q;i++)
    {
        int x=read(),y=read();
        if(x!=y) temp^=1;
        cout<<temp<<endl;
    }
    return 0;
}

 

 

 

 

 

T2 树的统计

题目

【题目描述】

给出一棵n个点的满二叉树，根节点为1，第i个点的左右子节点分别为第2i,2i+1个点，第i个点的权值为a[i]。

有m个询问。对于每个询问给出x,d，求到点x的距离为d的所有点的点权和。如果不存在符合条件的点，输出0。

两点距离即两点间最短路径的边数。

保证最终答案在int范围内。

【输入格式】

第一行两个正整数n,m。

接下来n行每行一个正整数，第i行的数表示a[i]。

接下来m行每行两个整数x,d，表示一个询问。

【输出格式】

对于每个询问输出一行表示答案。

【输入样例】

7 3
13
7
2
9
5
6
8
1 3
4 2
3 1

【输出样例】

0
18
27

【数据规模】

对于80%的数据，n≤1023，m≤1000。

对于100%的数据，n≤131071，m≤100000，n=2^t-1，1≤t≤17，a[i]≤30000。

解析

对于每个询问，用dfs搜索与点x距离为d的点，进行统计即可。

注意每个点之间的关系，访问父亲是x<<1，左儿子是x>>1，右儿子是x>>1+1，要特判一下左右儿子编号不能大于n，否则会RE。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
const int N=131073;
int n,m,a[N],dd,ans;
void dfs(int x,int d,int from)
{
    if(d>dd) return ;
    if(d==dd)
    {
        ans+=a[x];
        return ;
    }
    int y=x>>1;
    if(y>=1&&y!=from) dfs(y,d+1,x);
    y=x<<1;
    if(y<=n&&y!=from) dfs(y,d+1,x);
    if(y+1<=n&&y+1!=from) dfs(y+1,d+1,x);
}
int main()
{
    //freopen("dream.in","r",stdin);
    //freopen("dr