引述

序列中，对于每个i，统计满足 a[j]<a[i] )的时间。所以我们在每次递归前都把本次所有修改操作反向做一遍，这样的时间效率是O(nlog 2 n)。 这里只给出分治部分的代码，结构体声明、排序和树状数组请读者自行完成

快排法代码

void cdq(int l=1,int r=cnto) { int p1=l; int p2=mid+1; for(int i=l;i<=r;i++) { if(o[i].t<=mid&&!o[i].qid) bit.add(o[i].b,1); if(o[i].t>mid&&o[i].qid) ans[o[i].qid]+=bit.getsum(o[i].b); } for(int i=l;i<=r;i++) if(o[i].t<=mid&&!o[i].qid) bit.add(o[i].b,-1); for(int i=l;i<=r;i++) if(o[i].t<=mid) aux[p1++]=o[i]; else aux[p2++]=o[i]; for(int i=l;i<=r;i++) o[i]=aux[i]; if(l<mid)cdq(l,mid); if(mid+1<r)cdq(mid+1,r); }

归并法代码

声明：此份代码非博主本人完成，仅供参考和理解

void solve(int l,int r) { int mid; int f1; int f2; if(l==r) return; mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); for(f1=l,f2=mid+1;(f1<=mid)&&(f2<=r);) if(szp[f1].x<=szp[f2].x) { if(szp[f1].l==0) adds(szp[f1].y,szp[f1].d); f1++; } else { if(szp[f2].l!=0) sza[szp[f2].d]+=gets(szp[f2].y)*szp[f2].l; f2++; } for(;f2<=r;f2++) if(szp[f2].l!=0) sza[szp[f2].d]+=gets(szp[f2].y)*szp[f2].l; for(f1--;f1>=l;f1--) if(szp[f1].l==0) adds(szp[f1].y,-szp[f1].d); totn=l; for(f1=l,f2=mid+1;(f1<=mid)&&(f2<=r);) if(szp[f1].x<=szp[f2].x) szn[totn++]=szp[f1++]; else szn[totn++]=szp[f2++]; for(;f1<=mid;f1++) szn[totn++]=szp[f1]; for(;f2<=r;f2++) szn[totn++]=szp[f2]; for(f1=l;f1<=r;f1++) szp[f1]=szn[f1]; return; }

完结撒花