CF1093E Intersection of Permutations

III.CF1093E Intersection of Permutations

首先，我们如果令\(c[i]\)表示\(b[i]\)在数组\(a\)中出现的位置，

那么对于一次询问，答案就是\(c\)中下标在\([l_2,r_2]\)间的数字中，值位于\([l_1,r_1]\)间的数量。

思路1.树状数组套权值线段树。

很明显，这题的操作如果不带修可以用主席树完成（下标在\([l_2,r_2]\)里面的树上进行值域查询）。带了修改，则套上树状数组完事。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,root[200100],cnt,bin[10010000],tp,num[200100],a[200100],b[200100];
struct node{
	int lson,rson,sum;
}seg[20001000];
int newid(){
	if(!tp)return ++cnt;
	return bin[tp--];
}
void ADD(int &x,int l,int r,int P,int val){
	if(l>P||r<P)return;
	if(!x)x=newid();
	seg[x].sum+=val;
	if(l!=r)ADD(seg[x].lson,l,mid,P,val),ADD(seg[x].rson,mid+1,r,P,val);
	if(!seg[x].sum)bin[++tp]=x,x=0;
}
void add(int x,int y,int z){
	while(x<=n)ADD(root[x],1,n,y,z),x+=x&-x;
}
int Query(int x,int l,int r,int L,int R){
	if(!x||l>R||r<L)return 0;
	if(L<=l&&r<=R)return seg[x].sum;
	return Query(seg[x].lson,l,mid,L,R)+Query(seg[x].rson,mid+1,r,L,R);
}
int ask(int l,int r,int L,int R){
	l--;
	int res=0;
	while(r)res+=Query(root[r],1,n,L,R),r-=r&-r;
	while(l)res-=Query(root[l],1,n,L,R),l-=l&-l;
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),a[x]=i;
	for(int i=1,x;i<=n;i++)scanf("%d",&x),b[i]=a[x];
	for(int i=1;i<=n;i++)add(i,b[i],1);
	for(int i=1,t1,t2,t3,t4,t5;i<=m;i++){
		scanf("%d",&t1);
		if(t1==1)scanf("%d%d%d%d",&t2,&t3,&t4,&t5),printf("%d\n",ask(t4,t5,t2,t3));
		else scanf("%d%d",&t2,&t3),add(t2,b[t2],-1),add(t3,b[t3],-1),swap(b[t2],b[t3]),add(t2,b[t2],1),add(t3,b[t3],1);
	}
	return 0;
}

思路2.奇奇怪怪的分块-ver1.0

我们在数组\(c\)上分块，在每个块内排序。每次整块二分，散块直接暴力，复杂度\(O(n\sqrt{n}\log n)\)。

因为实现很糟糕，因此它T掉了。

TLE代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int BBB=600;
int n,m,BLK[200100],ra[200100],c[200100],d[200100],lp[1000],lim;
inline void SWAP(int x,int y){
	swap(c[x],c[y]);
	for(register int i=lp[BLK[x]];i<lp[BLK[x]+1];i++)d[i]=c[i];
	sort(d+lp[BLK[x]],d+lp[BLK[x]+1]);
	for(register int i=lp[BLK[y]];i<lp[BLK[y]+1];i++)d[i]=c[i];
	sort(d+lp[BLK[y]],d+lp[BLK[y]+1]);
}
inline int CALC(int l,int r,int L,int R){
	register int res=0;
	if(BLK[L]==BLK[R]){
		for(register int i=L;i<R;i++)res+=(c[i]>=l&&c[i]<r);
		return res;
	}
	for(register int i=L;i<lp[BLK[L]+1];i++)res+=(c[i]>=l&&c[i]<r);
	for(register int i=lp[BLK[R]];i<R;i++)res+=(c[i]>=l&&c[i]<r);
	for(register int i=BLK[L]+1;i<BLK[R];i++)res+=lower_bound(d+lp[i],d+lp[i+1],r)-lower_bound(d+lp[i],d+lp[i+1],l);
	return res; 
}
inline void read(int &x){
	x=0;
	register char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline int read(){
	register int x=0;
	register char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
inline void print(int x){
	if(x<=9)putchar('0'+x);
	else print(x/10),putchar('0'+x%10);
}
int main(){
	read(n),read(m);
	for(register int i=0;i<n;i++)ra[read()]=i,BLK[i]=i/BBB;
	for(register int i=0;i<n;i++)c[i]=d[i]=ra[read()];
	lim=BLK[n-1]+1;
	for(register int i=0;i<lim;i++)lp[i]=i*BBB;
	lp[lim]=n,BLK[n]=lim;
	for(register int i=0;i<lim;i++)sort(d+lp[i],d+lp[i+1]);
	for(register int i=1,t1,t2,t3,t4,t5;i<=m;i++){
		read(t1);
		if(t1==1)read(t2),read(t3),read(t4),read(t5),t2--,t4--,print(CALC(t2,t3,t4,t5)),putchar('\n');
		else read(t2),read(t3),t2--,t3--,SWAP(t2,t3);
	}
	return 0;
}

思路3.奇奇怪怪的分块-ver2.0

设块长为\(k\)，我们分析一下各个操作的复杂度：

整块复杂度为\(O(k\log\dfrac{n}{k})=O(k\log n)\)

散块复杂度为\(O(\dfrac{n}{k})\)

修改复杂度为\(O(\dfrac{n}{k}\log\dfrac{n}{k})=\dfrac{n}{k}\log n\)

则当\(k=\sqrt{n}\)时复杂度最优，为\(O(\sqrt{n}\log n)\)。

我们如果只考虑询问复杂度的话，这个\(k\)是可以取到\(\sqrt{n\log n}\)的。关键是修改。

有两种思路。

  1. 考虑将修改也分块。将修改储存下来，每累计\(\sqrt{n\log n}\)个修改后，就暴力\(O(n\log n)\)全部推平重新排序。则每次询问时，只需要\(O(\sqrt{n\log n})\)遍历所有修改并更新答案即可。复杂度\(O(\sqrt{n\log n})\)。

  2. 原本的修改，我们是\(\dfrac{n}{k}\log n\)重新排序的；发现修改只作用于一个位置；故可以直接\(O(k)\)插入排序，或者直接套上std::set让修改优化到\(O(\log k)\)。（实际上，套上set后就已经相当于一种树套树了，是分块套平衡树）

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int BBB=1000;
int n,m,BLK[200100],ra[200100],c[200100],d[200100],lp[1000],lim;
vector<pair<int,int> >v;
inline int CALC(int l,int r,int L,int R){
	register int res=0;
	for(auto x:v){
		res-=(x.first>=L)&&(x.first<R)&&(c[x.first]>=l)&&(c[x.first]<r);
		res-=(x.second>=L)&&(x.second<R)&&(c[x.second]>=l)&&(c[x.second]<r);
		swap(c[x.first],c[x.second]);
		res+=(x.first>=L)&&(x.first<R)&&(c[x.first]>=l)&&(c[x.first]<r);
		res+=(x.second>=L)&&(x.second<R)&&(c[x.second]>=l)&&(c[x.second]<r);
	}
	for(int i=v.size()-1;i>=0;i--)swap(c[v[i].first],c[v[i].second]);
	if(BLK[L]==BLK[R]){
		for(register int i=L;i<R;i++)res+=(c[i]>=l&&c[i]<r);
		return res;
	}
	for(register int i=L;i<lp[BLK[L]+1];i++)res+=(c[i]>=l&&c[i]<r);
	for(register int i=lp[BLK[R]];i<R;i++)res+=(c[i]>=l&&c[i]<r);
	for(register int i=BLK[L]+1;i<BLK[R];i++)res+=lower_bound(d+lp[i],d+lp[i+1],r)-lower_bound(d+lp[i],d+lp[i+1],l);
	return res; 
}
void init(){
	for(auto x:v)swap(c[x.first],c[x.second]);
	v.clear();
	for(int i=0;i<n;i++)d[i]=c[i];
	for(int i=0;i<lim;i++)sort(d+lp[i],d+lp[i+1]);
}
inline void read(int &x){
	x=0;
	register char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline int read(){
	register int x=0;
	register char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
inline void print(int x){
	if(x<=9)putchar('0'+x);
	else print(x/10),putchar('0'+x%10);
}
int main(){
	read(n),read(m);
	for(register int i=0;i<n;i++)ra[read()]=i,BLK[i]=i/BBB;
	for(register int i=0;i<n;i++)c[i]=ra[read()];
	lim=BLK[n-1]+1;
	for(register int i=0;i<lim;i++)lp[i]=i*BBB;
	lp[lim]=n,BLK[n]=lim;
	init();
	for(register int i=1,t1,t2,t3,t4,t5;i<=m;i++){
		read(t1);
		if(t1==1)read(t2),read(t3),read(t4),read(t5),t2--,t4--,print(CALC(t2,t3,t4,t5)),putchar('\n');
		else read(t2),read(t3),t2--,t3--,v.push_back(make_pair(t2,t3));
		if(v.size()>=BBB)init();
	}
	return 0;
}

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Troverld/p/14611078.html