[CQOI2011] 动态逆序对
程序员文章站
2022-04-13 15:33:24
使用树状数组求出初态下出f[i]、g[i]表示位置小(大)于i且值大(小)于a[i]的元素个数。显然ans|初=sum f[i]=sum g[i]。 考虑第一个删去的点x,删去以后,ans减少f[x]+g[x];再考虑第二个删去的点y,删去以后,ans减少f[y]+g[y]?不,f[y]、g[y]中 ......
使用树状数组求出初态下出f[i]、g[i]表示位置小(大)于i且值大(小)于a[i]的元素个数。显然ans|初=sum f[i]=sum g[i]。
考虑第一个删去的点x,删去以后,ans减少f[x]+g[x];再考虑第二个删去的点y,删去以后,ans减少f[y]+g[y]?不,f[y]、g[y]中可能算上了x(此题里是必然),这{x,y}这一对已经在上一次删除时减掉了,所以ans减少f[y]+g[y]的同时,还应加上已删除的点中与y构成的“逆序对数”。以后删除的点同理;
假设当前正在删除元素x,设元素到位置的映射为id[x],设f1、g1为在已删的点中与x相比位置小(大)于i且值更大(小)于的点的个数,那么ans应该为ans-f[x]-g[x]+f1+g1。现考虑如何快速计算f1、g1。以计算f1为例:
一:将删除的点放在新序列b的相应位置,每次扫描b[1~id[x]]中有多少满足b[i]>x的点。
二:不放将序列b扩充为矩阵b[i,j],b[i,j]表示位置为i,值为j的元素是否已经被删除。每次n^2求矩阵b[1~id[x], x+1,n]的和
三:二中的b大小为n*n显然不行。考虑将b[i]改为一颗权值线段树(求一段值域内的元素个数),这样大小变为nlogn。
四:每一次删除一个点,会修改线段树b[id[x]~n],用时过久。不放对所有权值线段树的同一个区间求前缀和(实例:主席树)查询变为作差;这时修改线段树b[id[x]~n]相当于是单点修改更新前缀和,考虑使用树状数组来完成。
就是树状数组套权值线段树了。
#include <bits/stdc++.h> using namespace std; const int n=1e6+10; int n,m,tot; long long ans; int root[n],bit[n],id[n],a[n],f[n],g[n]; struct edge { int ls,rs,sum; } t[n*30]; void update(int&x,int l,int r,int w) { if(!x) x=++tot; t[x].sum+=(w!=0); if(l==r) return; int mid=(l+r)>>1; if(w<=mid) update(t[x].ls,l,mid,w); else update(t[x].rs,mid+1,r,w); } int l[n],cntl,r[n],cntr; int f1(int x,int y,int w) { cntl=cntr=0, x--; for(; x>0; x-=(x&-x)) l[++cntl]=root[x]; for(; y>0; y-=(y&-y)) r[++cntr]=root[y]; int l=1, r=n, ret=0; while(l!=r) { int mid=(l+r)>>1; if(w<=mid) { //右区间全满 for(int i=1; i<=cntl; ++i) ret-=t[t[l[i]].rs].sum; for(int i=1; i<=cntr; ++i) ret+=t[t[r[i]].rs].sum; for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].ls; for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].ls; r=mid; } else { for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].rs; for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].rs; l=mid+1; } } return ret; } int g1(int x,int y,int w) { cntl=cntr=0, x--; for(; x>0; x-=(x&-x)) l[++cntl]=root[x]; for(; y>0; y-=(y&-y)) r[++cntr]=root[y]; int l=1, r=n, ret=0; while(l!=r) { int mid=(l+r)>>1; if(mid<w) { //左区间全满 for(int i=1; i<=cntl; ++i) ret-=t[t[l[i]].ls].sum; for(int i=1; i<=cntr; ++i) ret+=t[t[r[i]].ls].sum; for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].rs; for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].rs; l=mid+1; } else { for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].ls; for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].ls; r=mid; } } return ret; } int sum(int x,int y=0) { for(; x>0; x-=(x&-x)) y+=bit[x]; return y; } void add(int x,int y) { for(; x<=n; x+=(x&-x)) bit[x]+=y; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) { scanf("%d",&a[i]); id[a[i]]=i; f[i]=sum(n)-sum(a[i]); add(a[i],1); ans+=f[i]; } for(int i=1; i<=n; ++i) bit[i]=0; for(int i=n; i>=1; --i) { g[i]=sum(a[i]); add(a[i],1); } update(root[0],1,n,0); for(int x; m--; ) { scanf("%d",&x); printf("%lld\n",ans); ans-=f[id[x]]-f1(1,id[x],x)+g[id[x]]-g1(id[x],n,x); for(int i=id[x]; i<=n; i+=(i&-i)) { update(root[i],1,n,x); } } return 0; }
上一篇: Linux MySql 安装与配置