#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int t[N+10],n; void add(int x,int v) { for(;x<=n;x+=x&-x) t[x]+=v; } int qsum(int x) { int ans=0; for(;x;x-=x&-x) ans+=t[x]; return ans; } struct node { int id,x,y,v; bool operator <(const node &t) const { return x<t.x; } }s[N]; int ans[N]; bool cmp(node a,node b) {return a.x<b.x;} void cdq(int l,int r) { if(l==r) return ; int mid=l+r>>1; cdq(l,mid);cdq(mid+1,r); sort(s+l,s+mid+1);sort(s+mid+1,s+r+1); int j=l; for(int i=mid+1;i<=r;i++) { while(j<=mid&&s[j].x<=s[i].x) { if(s[j].id==0) add(s[j].y,s[j].v); j++; } if(s[i].id) ans[s[i].id]+=s[i].v*qsum(s[i].y); } while(--j>=l) if(s[j].id==0) add(s[j].y,-s[j].v); } int m,pa[N],pb[N],a[N],b[N],cnt; int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]),pa[a[i]]=i; for(int i=1;i<=n;i++) scanf("%d",&b[i]),pb[b[i]]=i; for(int i=1;i<=n;i++) { s[++cnt]={0,pa[i],pb[i],1}; } int op,la,lb,ra,rb,x,y;int cntq=0; for(int i=1;i<=m;i++) { scanf("%d",&op); if(op==1) { scanf("%d%d%d%d",&la,&ra,&lb,&rb);la--;lb--; s[++cnt]={++cntq,ra,rb,1}; s[++cnt]={cntq,la,lb,1}; s[++cnt]={cntq,ra,lb,-1}; s[++cnt]={cntq,la,rb,-1}; } else { scanf("%d%d",&x,&y); if(x==y) continue; s[++cnt]={0,pa[b[x]],pb[b[x]],-1}; s[++cnt]={0,pa[b[y]],pb[b[y]],-1}; swap(b[x],b[y]);pb[b[x]]=x;pb[b[y]]=y; s[++cnt]={0,pa[b[x]],pb[b[x]],1}; s[++cnt]={0,pa[b[y]],pb[b[y]],1}; } } cdq(1,cnt); for(int i=1;i<=cntq;i++) printf("%d\n",ans[i]); }
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int t[N+10],n; void add(int x,int v) { for(;x<=n;x+=x&-x) t[x]+=v; } int qsum(int x) { int ans=0; for(;x;x-=x&-x) ans+=t[x]; return ans; } struct node { int id,x,y,v,tim; }s[N],temp[N]; int ans[N]; bool cmp(node a,node b) {return a.x<b.x||a.x==b.x&&a.tim<b.tim;} void cdq(int l,int r) { if(l==r) return ; int mid=l+r>>1; for(int i=l;i<=r;i++) { if(s[i].tim<=mid&&!s[i].id) add(s[i].y,s[i].v); if(s[i].tim>mid&&s[i].id) ans[s[i].id]+=s[i].v*qsum(s[i].y); } int L=l,R=mid+1; for(int i=l;i<=r;i++) { if(s[i].tim<=mid&&!s[i].id) add(s[i].y,-s[i].v); if(s[i].tim<=mid) temp[L++]=s[i]; else temp[R++]=s[i]; } for(int i=l;i<=r;i++) s[i]=temp[i]; cdq(l,mid);cdq(mid+1,r); } int m,pa[N],pb[N],a[N],b[N],cnt,ccnt; int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]),pa[a[i]]=i; for(int i=1;i<=n;i++) scanf("%d",&b[i]),pb[b[i]]=i; for(int i=1;i<=n;i++) { s[++cnt]=(node){0,pa[i],pb[i],1,cnt}; } int op,la,lb,ra,rb,x,y,cntq=0; for(int i=1;i<=m;i++) { scanf("%d",&op); if(op==1) { scanf("%d%d%d%d",&la,&ra,&lb,&rb);la--;lb--; s[++cnt]=(node){++cntq,ra,rb,1,cnt}; s[++cnt]=(node){cntq,la,lb,1,cnt}; s[++cnt]=(node){cntq,ra,lb,-1,cnt}; s[++cnt]=(node){cntq,la,rb,-1,cnt}; } else { scanf("%d%d",&x,&y); if(x==y) continue; s[++cnt]=(node){0,pa[b[x]],pb[b[x]],-1,cnt}; s[++cnt]=(node){0,pa[b[y]],pb[b[y]],-1,cnt}; swap(b[x],b[y]);pb[b[x]]=x;pb[b[y]]=y; s[++cnt]=(node){0,pa[b[x]],pb[b[x]],1,cnt}; s[++cnt]=(node){0,pa[b[y]],pb[b[y]],1,cnt}; } } sort(s+1,s+1+cnt,cmp); cdq(1,cnt); for(int i=1;i<=cntq;i++) printf("%d\n",ans[i]); }
E. Intersection of Permutations cdq
原文:https://www.cnblogs.com/bxd123/p/12295953.html