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].
逆序对的意思是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 }