[CF1093E]Intersection of Permutations
题目大意：
给定两个长度为\(n(n\le2\times10^5)\)的排列\(A,B\)。\(m(m\le2\times10^5)\)次操作，操作分为以下两种：
- 询问有多少同时在\(A_{[x,y]}\)和\(B_{[l,r]}\)中出现的数。
- 交换\(B_x\)与\(B_y\)。
思路：
令\(v[a[i]]=i,b[i]=v[b[i]]\)，这样询问就变成\([x,y]\)中有多少数在\(B_{[l,r]}\)中出现。
用树状数组+平衡树维护每个区间出现哪些数，询问时在平衡树中查找排名即可。
源代码：
#include<cstdio>
#include<cctype>
#include<climits>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=2e5+1;
int n,v[N],a[N];
using namespace __gnu_pbds;
using RBTree=tree<int,null_type,std::less<int>,rb_tree_tag,tree_order_statistics_node_update>;
class FenwickTree {
private:
RBTree t[N];
int lowbit(const int &x) const {
return x&-x;
}
int query(int p,const int &x,const int &y) const {
int ret=0;
for(;p;p-=lowbit(p)) {
const int L=*t[p].lower_bound(x);
const int R=*std::prev(t[p].upper_bound(y));
if(L<=R) ret+=t[p].order_of_key(R)-t[p].order_of_key(L)+1;
}
return ret;
}
public:
void init() {
for(register int i=1;i<=n;i++) {
t[i].insert(INT_MIN);
t[i].insert(INT_MAX);
}
}
void insert(int p,const int &x) {
for(;p<=n;p+=lowbit(p)) {
t[p].insert(x);
}
}
void erase(int p,const int &x) {
for(;p<=n;p+=lowbit(p)) {
t[p].erase(x);
}
}
int query(const int &l,const int &r,const int &x,const int &y) const {
return query(r,x,y)-query(l-1,x,y);
}
};
FenwickTree t;
int main() {
n=getint();
const int m=getint();
for(register int i=1;i<=n;i++) {
v[getint()]=i;
}
for(register int i=1;i<=n;i++) {
a[i]=v[getint()];
}
t.init();
for(register int i=1;i<=n;i++) {
t.insert(i,a[i]);
}
for(register int i=0;i<m;i++) {
const int opt=getint(),x=getint(),y=getint();
if(opt==1) {
const int l=getint(),r=getint();
printf("%d\n",t.query(l,r,x,y));
}
if(opt==2) {
t.erase(x,a[x]);
t.erase(y,a[y]);
std::swap(a[x],a[y]);
t.insert(x,a[x]);
t.insert(y,a[y]);
}
}
return 0;
}