bzoj3295: [Cqoi2011]动态逆序对

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3295 题解：cdq分治； 我们仔细想一想维护逆序对的时候我们用的不就是归并排序吗？而归并排序不就可以看作一种分治吗？ 于是此题走上正轨，我们可以用分治来写 怎么写？ 我们删除一个点，损失了什么？————1.这个点x之前比我大的个数记为big【x】，这个点x之后比我小的记作small【x】，那么损失：small【x】+big【x】； 于是对于一个点x1我们只要维护一下这样两个二维偏序：1.x2<x1 && y2>y1 2.x1<x2 && y1>y2 的（x1，y1）的数量于是就可以用cdq分治了啊 问题解决了吗？ 解决了，但是要注意我们要把删除的倒着做，为什么自己想想吧 毕竟写题还是要自己思考（好吧，只是我懒得写........） 有一个详细的博客：http://blog.csdn.net/u011542204/article/details/50571409 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #define N 100005 using namespace std; int read() { int x=0; char ch; bool bo=0; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') bo=1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); if (bo) return -x; return x; } int small[N],big[N],pos[N],n,m; long long ans[N]; struct s{ int x,t,y; }a[N],t[N]; struct data{ int t[N]; int lowbit(int p){ return p&-p; } void modify(int x,int v){for (int i=x; i<=n; i+=lowbit(i)) t[i]+=v; } int query(int x){int res=0; for (int i=x; i; i-=lowbit(i)) res+=t[i]; return res; } }T; void solve(int l,int r) { if (l>=r) return; int mid=(l+r)>>1,l1=l,l2=mid+1; for (int i=l; i<=r; i++) if (a[i].t<=mid) t[l1++]=a[i]; else t[l2++]=a[i]; for (int i=l; i<=r; i++) a[i]=t[i]; l1=l; for (int i=mid+1; i<=r; i++) { for (; a[l1].x<a[i].x&& l1<=mid; l1++) T.modify(a[l1].y,1); small[a[i].t]+=l1-l-T.query(a[i].y); } for (int i=l; i<l1; i++) T.modify(a[i].y,-1); l1=mid; for (int i=r; i>=mid+1; i--) { for (; a[l1].x>a[i].x&&l1>=l; l1--) T.modify(a[l1].y,1); big[a[i].t]+=T.query(a[i].y-1); } for (int i=mid; i>l1; i--) T.modify(a[i].y,-1); solve(l,mid); solve(mid+1,r); } int main() { n=read(); m=read(); for (int i=1; i<=n; i++) pos[a[i].y=read()]=i,a[i].x=i; int temp=n; for (int i=1; i<=m; i++) a[pos[read()]].t=temp--; for (int i=1; i<=n; i++) if (a[i].t==0) a[i].t=temp--; solve(1,n); ans[0]=0; for (int i=1; i<=n; i++) ans[i]=ans[i-1]+big[i]+small[i];//,cout<<ans[i-1]<<" "<<big[i]<<" "<<small[i]<<endl; for (int i=n; i>=n-m+1; i--) printf("%lld\n",ans[i]); } View Code