和动态逆序对有些类似 这题既可以以时间为第一维 也可以以x轴维第一维度 具体视题目而定
cdq分治只能求点对之间的影响 如果要变成整个序列的情况 那么可以用前缀和 一开始的原序列的id设置成0即可
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) /////////////////////////////////////// const int N=1e5+10; int n,m,t[N+200],cnt,a[N],b[N]; ll ans[N]; void add(int x,int v){for(;x<=N+100;x+=x&-x)t[x]+=v;} int qsum(int x){int ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;} struct node{int x,y,w,id;}s[N]; bool cmp(node a,node b){return a.x<b.x;} void cdq(int l,int r) { if(l==r)return ;int mid=(l+r)>>1; cdq(l,mid);cdq(mid+1,r); sort(s+l,s+mid+1,cmp);sort(s+mid+1,s+r+1,cmp); int j=l; rep(i,mid+1,r) { while(j<=mid&&s[j].x<=s[i].x)add(s[j].y,s[j].w),j++; ans[s[i].id]+=1ll*s[i].w*(qsum(N)-qsum(s[i].y)); } while(--j>=l)add(s[j].y,-s[j].w); j=mid; repp(i,r,mid+1) { while(j>=l&&s[j].x>=s[i].x)add(s[j].y,s[j].w),j--;; ans[s[i].id]+=1ll*s[i].w*qsum(s[i].y-1); } while(++j<=mid)add(s[j].y,-s[j].w); } int main() { cin>>n; rep(i,1,n) { int x;scanf("%d",&x);a[i]=b[i]=x; s[++cnt]=(node){i,x,1,0}; } sort(b+1,b+1+n); int nn=unique(b+1,b+1+n)-b-1; rep(i,1,n)a[i]=lower_bound(b+1,b+1+nn,a[i])-b, s[i].y=lower_bound(b+1,b+1+nn,s[i].y)-b; cin>>m; rep(i,1,m) { int x,y;scanf("%d%d",&x,&y); s[++cnt]=(node){x,a[y],1,i}; s[++cnt]=(node){y,a[x],1,i}; s[++cnt]=(node){x,a[x],-1,i}; s[++cnt]=(node){y,a[y],-1,i}; swap(a[x],a[y]); } cdq(1,cnt); rep(i,1,m) ans[i]+=ans[i-1]; rep(i,0,m)printf("%lld ",ans[i]); return 0; }