ACDream

先上题目：

A - Dynamic Inversions II

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

给出N个数a[1],a[2] ... a[N]，a[1]...a[N]是1-N的一个排列，即1 <= a[i] <= N且每个数都不相同。有M个操作，每个操作给出x,y两个数，你将a[x]，a[y]交换，然后求交换后数组的逆序对个数 % 2。
逆序对的意思是1 <= i < j <= N 且a[i] > a[j].

Input

多组数据，每组数据:

两个数N,M，接下来一行有N个数a[1]... a[N]

最后M行每行两个数x,y

1 <= N,M <= 10^5, 1 <= x < y <= N，1 <= a[i] <= N

Output

对于每组数据，输出M + 1行，第一行是开始时的逆序对数目 % 2，接下去M行每行一个数，表示这次修改后的逆序对数目 % 2

Sample Input

2 1
1 2
1 2

Sample Output

0
1

　　因为结果要求的是逆序对的二进制最低位是多少，所以我们需要分析一下变换了位置以后的就变化情况。
　　先求一次逆序对。

　　再分析情况，发现逆序对的奇偶性变化只有两个数之间的数会带来变化。


①　　　　······大····小······　　　　-->　　······小····大······
　　中间的数有三种情况：a.比大的大 b.比大的小，比小的大  c.比小的小
　　对于三种情况逆序对的变化情况：

		小		大
大	减少		减少		增加
小	增加		减少		减少

　　其中减少和增加的量是相等的，那就是说这样变化的结果是偶数对-1对。

②　　　　······小····大······　　　　-->　　······大····小······
　　中间的数有三种情况：a.比大的大 b.比大的小，比小的大  c.比小的小
　　对于三种情况逆序对的变化情况：

		小		大
大	增加		增加		减少
小	减少		增加		增加

　　其中减少和增加的量是相等的，那就是说这样变化的结果是偶数对+1对。

③　　　　······a····a······　　　　-->不变

　　所以我们需要做的是判断交换的两个数是不是相等，如果是相等就不变化奇偶性，否则奇偶性变化一次。

上代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define lowbit(x) (x & (-x))
 6 #define MAX 100002
 7 #define LL long long
 8 using namespace std;
 9  
10 int n,m;
11  
12 int c[MAX],a[MAX];
13  
14 void add(int x){
15     for(;x<=n;x+=lowbit(x)) c[x]++;
16 }
17  
18 LL sum(int x){
19     LL ans=0;
20     for(;x>0;x-=lowbit(x)) ans+=c[x];
21     return ans;
22 }
23  
24 int main()
25 {
26     int x,y;
27     LL s;
28     while(scanf("%d %d",&n,&m)!=EOF){
29         memset(c,0,sizeof(c));
30         s=0;
31         for(int i=1;i<=n;i++){
32             scanf("%d",&a[i]);
33             add(a[i]);
34             s+=sum(n)-sum(a[i]);
35         }
36         bool f=s&1;
37         if(f) puts("1");
38         else puts("0");
39         for(int i=0;i<m;i++){
40             scanf("%d %d",&x,&y);
41             if(x!=y && a[x]!=a[y]) f=f^1;
42             swap(a[x],a[y]);
43             if(f) puts("1");
44             else puts("0");
45         }
46     }
47     return 0;
48 }

Dynamic InversionsII