Codeforces 911D. Inversion Counting (数学、思维)

时间:2021-11-12 14:54:06

题目链接:Inversion Counting

题意:

   定义数列{ai|i=1,2,...,n}的逆序对如下:对于所有的1≤j<i≤n,若ai<aj,则<i,j>为一个逆序对。于是,对于一个数列a[1..n],给定m次操作。对于每一次操作,给定l,r(1≤l<r≤n),将序列a[l..r]倒置。求倒置后的逆序对的数量的奇偶性。

题解:

  假设现在我们有一个序列并翻转这个序列[l,r]区间里面的数。假设某个数的k值是指在这个值后面小于这个数的数的个数,其实我们可以发现对于[1,l-1]区间中所有的数的k值并没有变化,同样的对于[r+1,n]区间中的所有数的k值也没有变化。那么我们只用考虑[l,r]区间内k值的变化,对于[l,r]中的某个数x,那么x的k值等于[x,r] + [r+1,n]区间小于x的数的个数,那么后一个区间[r+1,n]的影响同样不变,那现在我们只用只用考虑[x,r]区间对x的k值的影响了,假设没有翻转前[l,r]区间k值为a,则翻转后k值为(r-l+1)*(r-l)/2 - a(可以自己验证一下~)。所以整个序列k值相当于从 k 变到了 (r-l+1)×(r-l)/2 - a,差就为(r-l+1)×(r-l)/2 - 2×a。因为2×a是偶数,对奇偶性没有影响,所以我们只用判断(r-l+1)×(r-l)/2的奇偶性,如果为奇数就会改变整个序列的k值数量的奇偶性,偶数则不变。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX_N = 3e3+9;
 4 int res[MAX_N][MAX_N];
 5 int vec[MAX_N];
 6 int main()
 7 {
 8     int N,M,T;
 9     while(cin>>N)
10     {
11         memset(res,0,sizeof(res));
12         for(int i=1;i<=N;i++)
13         {
14             scanf("%d",&vec[i]);
15         }
16         int sum = 0;
17         for(int i=1;i<N;i++)
18         {
19             for(int j=i+1;j<=N;j++)
20             {
21                 if(vec[j] < vec[i]) sum++;
22             }
23         }
24         int flag = 1;
25         if(sum%2) flag = 1;
26         else flag = 0;
27         cin>>M;
28         for(int i=0;i<M;i++)
29         {
30             int l,r;
31             scanf("%d%d",&l,&r);
32             int x = r-l+1;
33             int t = (x*(x-1)/2)%2;
34             flag ^=t;
35             if(flag) cout<<"odd"<<endl;
36             else cout<<"even"<<endl;
37         }
38 
39     }
40     return 0;
41 }