[CF1093E]Intersection of Permutations：树套树+pbds

分析

裸的二维数点，博主用树状数组套平衡树写的，顺便pbds真好用。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define lowbit(x) ((x)&(-(x)))
#define rin(i,a,b) for(int i=(a);i<=(b);i++)
#define rec(i,b) for(int i=(a);i>=(b);i--)
#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)
typedef long long LL;
using namespace std;
using namespace __gnu_pbds;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=200005;
int n,m,a[MAXN],b[MAXN],c[MAXN],ic[MAXN],pos[MAXN];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbt[MAXN];

inline void Ins(int x,int kk){
    for(int i=x;i<=n;i+=lowbit(i)) rbt[i].insert(kk);
}

inline void Del(int x,int kk){
    for(int i=x;i<=n;i+=lowbit(i)) rbt[i].erase(kk);
}

inline int Ask(int x,int lb,int rb){
    int ret=0;
    for(int i=x;i;i-=lowbit(i)){
        auto it=rbt[i].lower_bound(lb);
        if(it==rbt[i].end()) continue;
        int bg=*it;
        it=rbt[i].upper_bound(rb);
        if(it==rbt[i].begin()) continue;
        int ed=*(--it);
        ret+=rbt[i].order_of_key(ed)-rbt[i].order_of_key(bg)+1;
    }
    return ret;
}

inline int Ask(int la,int ra,int rb){
    return Ask(ra,lb,rb)-Ask(la-1,rb);
}

int main(){
    n=read(),m=read();
    rin(i,1,n) a[i]=read();
    rin(i,n) b[i]=read(),pos[b[i]]=i;
    rin(i,n) c[i]=pos[a[i]],ic[pos[a[i]]]=i;
    rin(i,n) Ins(i,c[i]);
    while(m--){
        int opt=read();
        if(opt==1){
            int la=read(),ra=read(),lb=read(),rb=read();
            printf("%dn",Ask(la,ra,rb));
        }
        else{
            int x=read(),y=read();
            Del(ic[x],x);Del(ic[y],y);
            Ins(ic[x],y);Ins(ic[y],x);
            swap(ic[x],ic[y]);
        }
    }
    return 0;
}