首页 > 代码库 > ACDream - Dynamic Inversions II

ACDream - Dynamic Inversions II

先上题目:

A - Dynamic Inversions II

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

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 11 21 2

Sample Output

01

  因为结果要求的是逆序对的二进制最低位是多少,所以我们需要分析一下变换了位置以后的就变化情况。
  先求一次逆序对。
  再分析情况,发现逆序对的奇偶性变化只有两个数之间的数会带来变化。

①    ······大····小······    -->  ······小····大······
  中间的数有三种情况: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