做这道题对自己很不满意啊，看起来就是很简单的两次cdq，居然搞了两中午，以后做三维偏序问题一定要明确x、y、z之间的大小关系。
这个代码写的很差，理论上应该是右边继承，被我搞成左边。
#include#include #include #include #include #include using namespace std;typedef long long LL;int n;LL s[110000];int lowbit(int x){ return x&-x;}void add(int x,int k){ while(x<=n) { s[x]+=k; x+=lowbit(x); }}LL getsum(int x){ LL ret=0; while(x>=1) { ret+=s[x]; x-=lowbit(x); } return ret;}//--------树状数组---------- struct node{ int x,y,z;//大小、顺序、删除时间 node(){z=0;}}a[110000],b[110000],t[110000];LL f[110000];void cdq(int l,int r)//小，后面，没有被删除 //大，前面，没有被删除 == 置反，大，后面，没有被删除 { if(l==r){ return ;} int mid=(l+r)/2; cdq(l,mid);cdq(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid&&j<=r) { if(a[i].y>a[j].y) { f[a[i].z]+=getsum(a[i].z); t[p++]=a[i++]; } else { add(a[j].z,1); t[p++]=a[j++]; } } while(i<=mid) { f[a[i].z]+=getsum(a[i].z); t[p++]=a[i++]; } while(j<=r) { add(a[j].z,1); t[p++]=a[j++]; } for(int j=mid+1;j<=r;j++)add(a[j].z,-1); for(int i=l;i<=r;i++)a[i]=t[i];}int main(){ freopen("inverse.in","r",stdin); freopen("inverse.out","w",stdout); int m,k; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&k); a[k].x=k;a[k].y=i; } for(int i=1;i<=m;i++) scanf("%d",&k), a[k].z=n-i+1; int cnt=m; for(int i=1;i<=n;i++) if(a[i].z==0)a[i].z=n-cnt, cnt++; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++)b[i]=a[i]; for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]); cdq(1,n); for(int i=1;i<=n;i++)b[i].y=n-b[i].y+1; for(int i=1;i<=n;i++)a[i]=b[i]; cdq(1,n); LL sum=0;for(int i=1;i<=n;i++)sum+=f[i]; for(int i=n;i>=n-m+1;i--) printf("%lld\n",sum), sum-=f[i]; return 0;}