Description

You are given two permutations $a$ and $b$, both consisting of $n$ elements. Permutation of $n$ elements is such a integer sequence that each value from $1$ to $n$ appears exactly once in it.

You are asked to perform two types of queries with them:

• $1 \ l_a \ r_a \ l_b \ r_b$ — calculate the number of values which appear in both segment $[l_a,r_a]$ of positions in permutation $a$ and segment $[l_b,r_b]$ of positions in permutation $b$;
• $2 \ x \ y$ — swap values on positions $x$ and $y$ in permutation $b$.

Print the answer for each query of the first type.

It is guaranteed that there will be at least one query of the first type in the input.

Code

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#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 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(){
for (int i=1;i<=n;++i)
for (int i=1;i<=n;++i)
for (int i=1,op,l,r,L,R;i<=m;++i){
if (op==1){
printf("%d\n",T.query(L-1,R,l-1,r));
}
if (op==2){
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);
}
}
} 

#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);
}
}