题解 P3157 【[CQOI2011]动态逆序对】

my blog: redbag.pw 写的cdq分治。 考虑删除一个数$i​$ ，$i​$对答案的影响只有$i​$产生的贡献和$i​$对后面产生的影响 $x$：删除时间，$y$：位置，$z$：权值 求$i'$的逆序对：$x>x'$，$y<y'$，$z>z'$，求出一个答案$f_i$ 考虑 $i'$ 对后面的影响：$x>x'$，$y>y'$，$z<z'$，求出一个答案$g_i$ 对于最后没有删除的点，根据位置随便加一个删除时间。 然后就是三位偏序了。 求 $f_i$ ，按照删除时间从大到小排序，左边排 $z$ ，树状数组更 $y$ 求 $g_i$ ，按照删除时间从大到小排序，左边排 $y$ ，树状数组更 $z$ 最后扫一遍，更答案。 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; int qmax(int &x,int y) {if (x<y) x=y;} int qmin(int &x,int y) {if (x>y) x=y;} int read() { char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s))); if(s=='-')base=-1,s=getchar(); while(isdigit(s)) { k=k*10+(s^'0'); s=getchar(); } return k*base; } void write(ll x) { if(x<0) { putchar('-'); write(-x); } else { if(x/10) write(x/10);putchar(x%10+'0'); } } const int maxn=1e5+100; const int maxm=5e4+100; int n,m; int b[maxn],c[maxn]; int t[maxn]; ll ans; struct node { int x,y,z;//x:删除的时间 y:pos z:值 int f,g; } a[maxn],A[maxn]; inline void xg(int x,int y) { while (x<=n) { *(t+x)+=y; x+=x&(-x); } } inline int qsum(int x) { int sum=0; while (x) { sum+=*(t+x); x-=x&(-x); } return sum; } bool cmp(node aa,node bb)//按照位置排序 { return aa.y<bb.y; } bool cmp1(node aa,node bb)//按照删除时间排 { return aa.x>bb.x; } bool cmp2(node aa,node bb) { return aa.x<bb.x; } void cdq(int x,int y) { if (x==y) return; int mid=(x+y)>>1; cdq(x,mid);cdq(mid+1,y); int l=x,r=mid+1,p=0; while (r<=y)//统答案 { while (l<=mid&&a[l].z>a[r].z) {xg(a[l].y,1);l++;} a[r].f+=qsum(a[r].y); r++; } for (int i=x;i<l;i++) xg(a[i].y,-1); l=x,r=mid+1,p=x-1;//归并 while (l<=mid&&r<=y) { if (a[l].z>a[r].z) A[++p]=a[l++]; else A[++p]=a[r++]; } while (l<=mid) A[++p]=a[l++]; while (r<=y) A[++p]=a[r++]; for (int i=x;i<=y;i++) a[i]=A[i]; } void CDQ(int x,int y) { if (x==y) return; int mid=(x+y)>>1; CDQ(x,mid);CDQ(mid+1,y); int l=x,r=mid+1,p=0; while (r<=y) { while (l<=mid&&a[l].y>a[r].y) {xg(a[l].z,1);l++;} a[r].g+=qsum(a[r].z); r++; } for (int i=x;i<l;i++) xg(a[i].z,-1);//memset太慢了，不如一个个清 l=x,r=mid+1,p=x-1;//按照y的大小合并 while (l<=mid&&r<=y) { if (a[l].y>a[r].y) A[++p]=a[l++]; else A[++p]=a[r++]; } while (l<=mid) A[++p]=a[l++]; while (r<=y) A[++p]=a[r++]; for (int i=x;i<=y;i++) a[i]=A[i]; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); n=read();m=read();//a数组初始按值排序 for (int i=1;i<=n;i++) { *(b+i)=read(); a[b[i]].y=i; a[b[i]].z=b[i]; ans+=i-1-qsum(b[i]); xg(b[i],1); } memset(t,0,sizeof(t)); for (int i=1;i<=m;i++) { *(c+i)=read(); a[c[i]].x=i; } sort(a+1,a+n+1,cmp); for (int i=1,j=m+1;i<=n;i++) { if (a[i].x==0) a[i].x=j++; } sort(a+1,a+n+1,cmp1); cdq(1,n);//求出f[i] sort(a+1,a+n+1,cmp1); CDQ(1,n);//求出g[i] sort(a+1,a+n+1,cmp2); for (int i=1;i<=m;i++) { write(ans); putchar('\n'); ans=ans-(ll)a[i].f-(ll)a[i].g; } return 0; } ```