【Codeforces】CF 911 D. Inversion Counting(逆序对+思维)

时间:2021-07-01 17:03:21

题目

传送门:QWQ

 

 

分析

思维要求比较高。

首先我们要把原图的逆序对q算出来。

这个树状数组或归并排序都ok(树状数组不用离散化好评)

那么翻转$[l,r]$中的数怎么做呢?

暴力过不了,我试过了。

设$ t=r-l+1 $即为区间长度

那么区间数对数量(看好是所有数对,不是逆序对)的数量就是$ k =\frac{n\times(n-1)}{2} $

方法是我们判断一下数量k的奇偶性,如果是奇数的,那么就把$ q $的奇偶性变一变。

然后判断q的奇偶性输出就行。

为什么这样是对的呢?

首先翻转区间只影响到了两个数都在这个区间里面的逆序对,不干涉其他的数对。 翻转区间后,逆序对变成了正序对,正序对变成了逆序对。

那么如果k是偶数,那么无论区间里面的逆序对的奇偶性如何,翻转后奇偶性都不变。比如k=8,区间里面的逆序对数量p=3,翻转后逆序对数量p=5,不改变奇偶性。p为偶数时也同理。

那么如果k是奇数呢?比如k=9, p=3,翻转后p=6,奇偶性改变了。而p为偶数时也同理。

综上,只要区间数对数量k为奇数,原序列的逆序对数量奇偶性就改变,否则则不改变。

 

 

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3500;
int bit[maxn];
int a[maxn], n;
void add(int x,int c){ while(x<=n){ bit[x]+=c; x+=x&-x; } }
int query(int x){
    int res=0;
    while(x){ res+=bit[x]; x-=x&-x; }
    return res;
}
int getRE(int l,int r){
    memset(bit,0,sizeof(bit));
    int ans=0;
    for(int i=l;i<=r;i++){
        ans+=i-l-query(a[i]);
        add(a[i],1);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int q=getRE(1,n)%2;
    int m; scanf("%d",&m);
    while(m--){
        int l,r; scanf("%d%d",&l,&r);
        int t=r-l+1; t=t*(t-1)/2;
        if(t%2) q^=1;
        if(!q) puts("even"); else puts("odd");
    }
}