题意：
交换序列中两个元素，求逆序对
做分块做到这道题...一看不是三维偏序嘛....
作为不会树套树的蒟蒻就写CDQ分治吧....
对时间分治...x排序...y树状数组...
交换拆成两个插入两个删除，保存一下类型就行了
才发现逆序对问题的删除操作不用时间倒流也可以，直接减去它形成的逆序对数并且在树状数组中删除就可以了
然后愚蠢的我竟然把操作的时间弄成相同的调了一会才觉得不对....
#include#include #include #include using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,Q,a[N],mp[N];int m,tim;struct meow{ int t,x,y,type,qid; meow(){} meow(int a,int b,int c,int d,int e=0):t(a),x(b),y(c),type(d),qid(e){} bool operator <(const meow &r) const{ return x==r.x ? y >1; for(int i=l;i<=r;i++){ if(q[i].t<=mid) add(q[i].y,q[i].type); else ans[q[i].qid]+= q[i].type*( sum(n)-sum(q[i].y) ); } for(int i=l;i<=r;i++) if(q[i].t<=mid) add(q[i].y,-q[i].type); for(int i=r;i>=l;i--){ if(q[i].t<=mid) add(q[i].y,q[i].type); else ans[q[i].qid]+= q[i].type*sum(q[i].y-1); } for(int i=l;i<=r;i++) if(q[i].t<=mid) add(q[i].y,-q[i].type); int p1=l,p2=mid+1; for(int i=l;i<=r;i++){ if(q[i].t<=mid) t[p1++]=q[i]; else t[p2++]=q[i]; } for(int i=l;i<=r;i++) q[i]=t[i]; CDQ(l,mid); CDQ(mid+1,r);}int main(){ freopen("in","r",stdin); n=read(); for(int i=1;i<=n;i++) a[i]=mp[i]=read(); sort(mp+1,mp+1+n); mp[0]=unique(mp+1,mp+1+n)-mp-1; for(int i=1;i<=n;i++) a[i]=lower_bound(mp+1,mp+1+mp[0],a[i])-mp, q[++m]=meow(++tim,i,a[i],1, 0); n=mp[0];//Look,here I changed the n. Q=read(); for(int i=1;i<=Q;i++){ int p1=read(),p2=read(); q[++m]=meow(++tim,p1,a[p2], 1, i); q[++m]=meow(++tim,p2,a[p1], 1, i); q[++m]=meow(++tim,p1,a[p1],-1, i); q[++m]=meow(++tim,p2,a[p2],-1, i); swap(a[p1],a[p2]); } sort(q+1,q+1+m); CDQ(1,m); printf("%d\n",ans[0]); for(int i=1;i<=Q;i++) ans[i]+=ans[i-1],printf("%d\n",ans[i]);}