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
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 #define ll long long 8 int a[110000],b[110000],n; 9 int lowbit(int x) 10 { 11 return x&(-x); 12 } 13 void update(int x) 14 { 15 while(x<=n) 16 { 17 b[x]++; 18 x+=lowbit(x); 19 } 20 } 21 int query(int x) 22 { 23 int sum=0; 24 while(x>0) 25 { 26 sum+=b[x]; 27 x-=lowbit(x); 28 } 29 return sum; 30 } 31 int main() 32 { 33 int m,i,x,y; 34 ll ans; 35 while(~scanf("%d%d",&n,&m)) 36 { 37 ans=0; 38 memset(b,0,sizeof(b)); 39 for(i=1; i<=n; i++) 40 { 41 scanf("%d",&a[i]); 42 update(a[i]); 43 ans+=i-query(a[i]); 44 } 45 printf("%lld\n",ans&1); 46 ans&=1; 47 for(i=0; i<m; i++) 48 { 49 scanf("%d%d",&x,&y); 50 ans^=1; 51 printf("%lld\n",ans); 52 } 53 } 54 }