题目：http://codeforces.com/contest/1093/problem/E
只能想到转化成查询一个区间里值在一个范围里的数的个数……
没有想到这样适合用主席树套树状数组维护。不过据说卡空间。
参考了这里的题解：https://www.luogu.org/problemnew/solution/CF1093E
写了CDQ分治。一个值在两个序列里的位置看成两维坐标的话，就是查平面区域内点的个数。
按 x (在第一个序列里的位置)排序，分治操作的时间，y (在第二个序列里的位置)用树状数组解决。
做这一层的时候要先枚举，再消除影响，然后再把 a[ ] 分成两部分。这样才能保证贡献给这个询问的是 x 在它之前、时间在它之前的那些 y 。在树状数组里就不考虑 x 了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+;
int n,m,ta[N],tb[N],pa[N],pb[N],ans[N],tot,f[N],cnt;
struct Node
{
bool fx;int x,y,k,id,tim;
Node(bool f=,int x=,int y=,int k=,int i=,int t=):
fx(f),x(x),y(y),k(k),id(i),tim(t) {}
bool operator< (const Node &b)const
{return x<b.x||(x==b.x&&tim<b.tim);}
}a[(N<<)+N],b[(N<<)+N];//+N
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
void add(int x,int k){for(;x<=n;x+=(x&-x))f[x]+=k;}
int query(int x){int ret=;for(;x;x-=(x&-x))ret+=f[x];return ret;}
void solve(int l,int r)
{
if(l>=r)return;
int mid=l+r>>,p0=l,p1=mid+;
for(int i=l;i<=r;i++)
if(!a[i].fx&&a[i].tim<=mid)add(a[i].y,a[i].k);
else if(a[i].fx&&a[i].tim>mid)ans[a[i].id]+=a[i].k*query(a[i].y);
for(int i=l;i<=r;i++)
if(!a[i].fx&&a[i].tim<=mid)add(a[i].y,-a[i].k);
for(int i=l;i<=r;i++)
if(a[i].tim<=mid)b[p0++]=a[i];
else b[p1++]=a[i];
for(int i=l;i<=r;i++)a[i]=b[i];
solve(l,mid); solve(mid+,r);
}
int main()
{
n=rdn();m=rdn();
for(int i=;i<=n;i++)ta[i]=rdn(),pa[ta[i]]=i;
for(int i=;i<=n;i++)tb[i]=rdn(),pb[tb[i]]=i;
for(int i=;i<=n;i++)
a[++cnt]=Node(,pa[i],pb[i],,,cnt);//
for(int i=,op,x1,y1,x2,y2,w1,w2;i<=m;i++)
{
op=rdn();
if(op==)
{
tot++;
x1=rdn();x2=rdn();y1=rdn();y2=rdn();
x1--; y1--;
a[++cnt]=Node(,x2,y2,,tot,cnt);
a[++cnt]=Node(,x1,y2,-,tot,cnt);
a[++cnt]=Node(,x2,y1,-,tot,cnt);
a[++cnt]=Node(,x1,y1,,tot,cnt);
}
else
{
int w1=rdn(),w2=rdn();
y1=w1;x1=pa[tb[w1]];y2=w2;x2=pa[tb[w2]];
swap(pb[tb[w1]],pb[tb[w1]]);
swap(tb[w1],tb[w2]);
a[++cnt]=Node(,x1,y1,-,,cnt);
a[++cnt]=Node(,x2,y2,-,,cnt);
a[++cnt]=Node(,x1,y2,,,cnt);
a[++cnt]=Node(,x2,y1,,,cnt);
}
}
sort(a+,a+cnt+);
solve(,cnt);
for(int i=;i<=tot;i++)printf("%d\n",ans[i]);
return ;
}