Menu
Article

【Codeforces 1093E】Intersection of Permutations / 题解

Zepto

Zepto

• 4 min read

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.

Idea

看到这道题我第一个想法就是：带修改主席树。

令 $p_i$ 代表 $a_i$ 在 $b$ 中出现的位置，每次询问就是求区间 $[l_a,r_a]$ 中，权值在 $[l_b,r_b]$ 之间的数字个数，修改就是简单的单点修改。

静态主席树的写法大家非常清楚，我把它理解为前缀权值线段树。如何动态维护一个前缀数组呢？采用树状数组即可。我写的带修改主席树本质就是树状数组套主席树，树状数组上每个节点对应储存了相应区间信息的主席树。

这样写实测过不了。原因很简单，空间不够。但是这个东西还是很有用的（我写的也很好看），代码放在文章末尾了。

如何在 Codeforces 上通过此题？把主席树换成 $\text{pbds}$ 里的 红黑树 即可。

Code

以下是在 Codeforces 上可以通过的代码。

#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 read(){
	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(){
	n=read(),m=read();
	for (int i=1;i<=n;++i)
		a[i]=read(),p[a[i]]=i;
	for (int i=1;i<=n;++i)
		b[i]=read(),b[i]=p[b[i]],T.update(i,b[i],1);
	for (int i=1,op,l,r,L,R;i<=m;++i){
		op=read();
		if (op==1){
			l=read(),r=read(),L=read(),R=read();
			printf("%d\n",T.query(L-1,R,l-1,r));
		}
		if (op==2){
			l=read(),r=read();
			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);
	}
}
Share