出题人题解 | #tokitsukaze and Inverse Number#

原题解链接：https://ac.nowcoder.com/discuss/150249

先树状数组求逆序数，然后有个结论。

结论: $11$到$nn$的排列，任意交换两个数，逆序数奇偶性发生改变。

$ansans$=(操作前的序列的逆序数+需要交换多少次才能变成操作后的序列(不需要求最小操作次数))%$22$。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
struct BIT{
    int val[maxn];
    int lowbit(int x){
        return x & -x;
    }
    void add(int x){
        while (x<maxn){
            val[x] ++;
            x += lowbit(x);
        }
    }
    int query(int x){
        int ans =0;
        while (x){
            ans += val[x];
            x -= lowbit(x);
        }
        return ans;
    }
}tree;
int a[maxn];
int main(){
    int n;
    scanf("%d",&n);
    int sum = 0;
    for (int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    for (int i=n-1;i>=0;i--){
        sum += tree.query(a[i]);
        sum %=2;
        tree.add(a[i]);
    }
    int m;
    scanf("%d",&m);
    while (m--){
        int l,r,k,len;
        scanf("%d%d%d",&l,&r,&k);
        len = r-l+1;
        int A = k % len;
        int B = len - A;
        //cerr<<A<<" "<<B<<endl;
        int delta = A%2 * B%2;
        delta %=2;
        if (delta){
            sum ^=1;
        }
        printf("%d\n",sum);
    }
    return 0;
}