题解 CF1093E 【Intersection of Permutations】
XG_Zepto
2018-12-18 21:52:35
文章首发于 [个人博客](https://zepto.page/post/codeforces-1093e)。
### 思路
看到这道题我第一个想法就是：带修改主席树。
令 $p_i$ 代表 $b_i$ 在 $a$ 中出现的位置，每次询问就是求区间 $[l_b,r_b]$ 中，权值在 $[l_a,r_a]$ 之间的数字个数，修改就是简单的单点修改。
静态主席树的写法大家非常清楚，我把它理解为前缀权值线段树。如何动态维护一个前缀数组呢？采用树状数组即可。我写的带修改主席树本质就是树状数组套主席树，树状数组上每个节点对应储存了相应区间信息的主席树。
这样写实测过不了。原因很简单，空间不够。但是这个东西还是很有用的（~~我写的也很好看~~），代码放在文章末尾了。
如何在 Codeforces 上通过此题？把主席树换成 $\text{pbds}$ 里的 红黑树 即可。
### 代码
以下是在 Codeforces 上可以通过的代码。
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
#define maxn 2000100
#define pi pair<int,int>
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <class T> using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int read(){
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
template <int size> struct rbtree{
Tree<int> val[size+1];
void update(int pos,int tag,int op){
while(pos<=size){
if (op) val[pos].insert(tag);
else val[pos].erase(tag);
pos+=(pos&-pos);
}
}
int query(int pos,int tag){
int res=0;
while(pos){
res+=val[pos].order_of_key(tag+1);
pos-=(pos&-pos);
}
return res;
}
int query(int l,int r,int L,int R){
return query(r,R)-query(r,L)-query(l,R)+query(l,L);
}
};
rbtree<maxn>T;
int n,m,a[maxn],b[maxn],p[maxn];
int main(){
n=read(),m=read();
for (int i=1;i<=n;++i)
a[i]=read(),p[a[i]]=i;
for (int i=1;i<=n;++i)
b[i]=read(),b[i]=p[b[i]],T.update(i,b[i],1);
for (int i=1,op,l,r,L,R;i<=m;++i){
op=read();
if (op==1){
l=read(),r=read(),L=read(),R=read();
printf("%d\n",T.query(L-1,R,l-1,r));
}
if (op==2){
l=read(),r=read();
T.update(l,b[l],0);T.update(r,b[r],0);
swap(b[l],b[r]);
T.update(l,b[l],1);T.update(r,b[r],1);
}
}
}
```
以下是带修改主席树，在极限数据下爆空间了。
```cpp
#include <bits/stdc++.h>
#define maxn 200100
#define mid ((l+r)>>1)
#define logn 100
int rt[maxn],ts[maxn*135],ls[maxn*135],rs[maxn*135];
int a[maxn],b[maxn],A[maxn],B[maxn],C[maxn],la,lb,cnt,n,m;
void update(int &p,int f,int l,int r,int x,int v){
if (!p) p=++cnt;ts[p]+=v;
if (l>=r) return;
if (mid>=x) update(ls[p],p,l,mid,x,v);
else update(rs[p],p,mid+1,r,x,v);
}
int query(int p,int l,int r,int L,int R){
if (L<=l&&r<=R) return ts[p];
if (mid>=R) return query(ls[p],l,mid,L,R);
if (mid<L) return query(rs[p],mid+1,r,L,R);
return query(ls[p],l,mid,L,R)+query(rs[p],mid+1,r,L,R);
}
void change(int x,int y){
int fx=B[x],fy=B[y];
for (int i=fx;i<=n;i+=(i&-i)) update(rt[i],0,1,n,x,-1);
for (int i=fy;i<=n;i+=(i&-i)) update(rt[i],0,1,n,y,-1);
for (int i=fx;i<=n;i+=(i&-i)) update(rt[i],0,1,n,y,1);
for (int i=fy;i<=n;i+=(i&-i)) update(rt[i],0,1,n,x,1);
std::swap(B[x],B[y]);
}
void get(int l,int r,int L,int R){
int sum=0;l--;
for (int i=l;i;i-=(i&-i)) sum-=query(rt[i],1,n,L,R);
for (int i=r;i;i-=(i&-i)) sum+=query(rt[i],1,n,L,R);
printf("%d\n",sum);
}
int main(){
freopen("test.in","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%d",a+i);
for (int i=1;i<=n;++i) scanf("%d",b+i);
for (int i=1;i<=n;++i) B[b[i]]=i;
for (int i=1;i<=n;++i) A[i]=B[a[i]];
for (int i=1;i<=n;++i) C[a[i]]=i;
for (int i=1;i<=n;++i) B[i]=C[b[i]];
for (int i=1;i<=n;++i)
for (int j=i;j<=n;j+=(j&-j))
update(rt[j],0,1,n,A[i],1);
for (int i=1,op,a,b,c,d;i<=m;++i){
scanf("%d",&op);
if (op==2) scanf("%d%d",&a,&b),change(a,b);
if (op==1) scanf("%d%d%d%d",&a,&b,&c,&d),get(a,b,c,d);
}
}
```