Codeforces1093E_Intersection of Permutations
2011 年 1 月 7 日
题意
给定两个排列a和b,两种操作,交换b_i和b_j,询问a[l_a…r_a]和b[l_b…r_b]有多少个数相同。
分析
给定两个排列a和b,两种操作,交换b_i和b_j,询问a[l_a…r_a]和b[l_b…r_b]有多少个数相同。
分析
- 由于给的是排列,保证b的每个数都有a的对应,构造数组c,c[i]表示b[i]在a数组中的位置。
- 所以询问就变成询问c[l_b…r_b]中有多少个值域为[l_a…r_b]的数,树套树…
- 内层的权值线段树动态开点一不小心就RE在第22个点,写了可回收的方式才过。
- 代码10分钟,debug两节课…
代码
#include using namespace std; const int N=2e5+50; int n,m,tr[N],a[N],p[N],b[N],c[N],o,la,ra,lb,rb,xi,yi,x[N],y[N],c1,c2,sta[N],top; struct VST{ #define mid (l+r)/2 int tot,sum[N*180],ls[N*180],rs[N*180]; //回收节点 int newnode(){ int p=top?sta[--top]:++tot; ls[p]=rs[p]=sum[p]=0; return p; } void update(int &x,int l,int r,int v,int add){ if(!x){ x=newnode(); } sum[x]+=add; if(l<r){ if(v<=mid){ update(ls[x],l,mid,v,add); }else{ update(rs[x],mid+1,r,v,add); } } //回收节点 if(!sum[x]){ sta[top++]=x; x=0; } } int query(int l,int r,int k){ if(k==0){ return 0; } if(r<=k){ int ans=0; for(int i=1;i<=c1;i++){ ans-=sum[x[i]]; } for(int i=1;i<=c2;i++){ ans+=sum[y[i]]; } return ans; } if(k<=mid){ for(int i=1;i<=c1;i++){ x[i]=ls[x[i]]; } for(int i=1;i<=c2;i++){ y[i]=ls[y[i]]; } return query(l,mid,k); }else{ int ans=0; for(int i=1;i<=c1;i++){ ans-=sum[ls[x[i]]]; x[i]=rs[x[i]]; } for(int i=1;i<=c2;i++){ ans+=sum[ls[y[i]]]; y[i]=rs[y[i]]; } return ans+query(mid+1,r,k); } } }ac; struct BIT{ int lowbit(int x){ return x&(-x); } void update(int i,int x){ int k=c[i]; while(i<=n){ ac.update(tr[i],1,n,k,x); i+=lowbit(i); } } int query(int l,int r,int xi,int yi){ c1=c2=0; for(int i=l-1;i;i-=lowbit(i)){ x[++c1]=tr[i]; } for(int i=r;i;i-=lowbit(i)){ y[++c2]=tr[i]; } int R=ac.query(1,n,yi); c1=c2=0; for(int i=l-1;i;i-=lowbit(i)){ x[++c1]=tr[i]; } for(int i=r;i;i-=lowbit(i)){ y[++c2]=tr[i]; } int L=ac.query(1,n,xi-1); return R-L; } }bit; int main(){ // freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); p[a[i]]=i; } for(int i=1;i<=n;i++){ scanf("%d",&b[i]); c[i]=p[b[i]]; bit.update(i,1); } for(int i=1;i<=m;i++){ scanf("%d",&o); if(o==1){ scanf("%d%d%d%d",&la,&ra,&lb,&rb); int ans=bit.query(lb,rb,la,ra); printf("%d\n",ans); }else if(o==2){ scanf("%d%d",&xi,&yi); bit.update(xi,-1); bit.update(yi,-1); swap(c[xi],c[yi]); bit.update(xi,1); bit.update(yi,1); } } return 0; }