逆序对

做法

任意交换两个数后，逆序对数的奇偶性改变

先求出原始序列的逆序对数的奇偶性(可以通过归并排序或者树状数组的方法求逆序对数)

对于操作1==>交换1次(l与r不相等)
对于操作2==>对半交换
对于操作3==>依次向左（或向右）逐位交换

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int a[N],b[N];
long long res=0; 
void merge_sort(int a[],int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;

    merge_sort(a,l,mid), merge_sort(a,mid+1,r);

    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]) b[k++]=a[i++];
        else{
            res+=mid-i+1;
            b[k++]=a[j++];
        }
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    merge_sort(a,1,n);
    res&=1;
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            if(l!=r) res^=1;
        }
        else if(op==2){
            int l,r;cin>>l>>r;
            int len=r-l+1;
            if((len>>1)&1) res^=1;
        }
        else{
            int l,r,k;cin>>l>>r>>k;
            int len=r-l+1;
            if((k*(len-1))&1) res^=1;
        }
        cout<<res<<"\n";
    }
    return 0;
}