CF1181D Irrigation Intersection of Permutations

题目链接
题意：给你两个长度为n,m的排列a,b，然后让你支持两个操作：
1.询问a排列上[l1,r1]区间和b排列上[l2,r2]区间相同元素的个数。
2.交换b排列上c,d位置的元素

思路 ：我们可以建立一个长度m的数组c，其中第 $i$i个元素表示b[i]在a中的位置，那么显然答案就是c数组[l2,r2]中值在[l1,r1]的个数了。
直接上树状数组套主席树即可在线解决这个问题，注意要回收空间。

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 3;
const LL mod = 1e9 + 7;
int n,m,a[N],b[N],A[N],B[N],T[N],tot,Q[N*40],cnt;
struct uzi{int sum,l,r;}t[N*170];
int newnode(){int p=tot?Q[tot--]:++cnt;t[p].sum=t[p].l=t[p].r=0;return p;}
void up(int &x,int y,int l,int r,int p,int v){
    if(!x){x=newnode();}t[x].sum+=v;
    if(l==r)return ;int mid=l+r>>1;
    if(p<=mid)up(t[x].l,t[y].l,l,mid,p,v);
    else up(t[x].r,t[y].r,mid+1,r,p,v);
    if(!t[x].sum)Q[++tot]=x,x=0;
}
int get(int o,int l,int r,int x,int y){
    if(x<=l&&y>=r)return t[o].sum;
    int mid=l+r>>1,ans=0;
    if(x<=mid)ans+=get(t[o].l,l,mid,x,y);
    if(y>mid)ans+=get(t[o].r,mid+1,r,x,y);
    return ans;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),A[a[i]]=i;
	for(int i=1;i<=n;i++)scanf("%d",&b[i]),B[b[i]]=i;
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=j&-j)up(T[j],T[j],1,n,B[a[i]],1);
	for(int i=1;i<=m;i++){
	    int o,la,ra,lb,rb;
	    cin>>o;
	    if(o==1){
	        scanf("%d%d%d%d",&la,&ra,&lb,&rb);
	        int ANS=0;
	        for(int j=la-1;j;j-=j&-j)ANS-=get(T[j],1,n,lb,rb);
	        for(int j=ra;j;j-=j&-j)ANS+=get(T[j],1,n,lb,rb);
	        printf("%d\n",ANS);
	    }else{
	        scanf("%d%d",&la,&lb);
	        int pA=A[b[la]],pB=A[b[lb]];
	        for(int j=pA;j<=n;j+=j&-j)up(T[j],T[j],1,n,B[b[la]],-1);
            for(int j=pB;j<=n;j+=j&-j)up(T[j],T[j],1,n,B[b[lb]],-1);
            swap(b[la],b[lb]);
            B[b[la]]=la;
            B[b[lb]]=lb;
            pA=A[b[la]];
            pB=A[b[lb]];
            for(int j=pA;j<=n;j+=j&-j)up(T[j],T[j],1,n,B[b[la]],1);
            for(int j=pB;j<=n;j+=j&-j)up(T[j],T[j],1,n,B[b[lb]],1);
	    }
	}
	return 0;
}