Codeforces 1093E Intersection of Permutations (CDQ分治+树状数组）

题意：给你两个数组a和b，a,b都是一个n的全排列；有两种操作:一种是询问区间在数组a的区间[l1,r1]和数组b的区间[l2,r2]出现了多少相同的数字，另一种是交换数组b中x位置和y位置的数字。

思路：我们可以建立数组b对数组a的映射mp,mp[x]表示数组b中x位置的数在数组a中出现的位置，这样问题转化为了带修改的询问一个矩形内点的个数的问题。想法是树套树，但是这题卡常，很多树套树会被卡掉，介于本辣鸡的代码能力，很容易写丑，所以用CDQ分治。

此问题和三维偏序问题很像（把每个操作的时间看作一维）。

代码的实现参考了这篇博客：http://www.cnblogs.com/mlystdcall/p/6219421.html

之后我补了此题的树套树做法：https://www.cnblogs.com/pkgunboat/p/10220821.html

代码：

#include<cstdio>

#include<algorithm>

#include<vector>

#include<iostream>

#include<cstring>

using namespace std;

const int maxn=200010;

struct Query{

	int type,x,y,flag,num,cnt;//操作类型,x,y,+还是-,第几个询问

	bool operator <(const Query& rhs)const{

		return x==rhs.x?type<rhs.type:x<rhs.x;

	}

}; 

Query query[maxn*10],tmp[maxn*10];

int tot=0,ans[maxn],a[maxn],b[maxn],p[maxn],mp[maxn],n,m;

namespace BIT{

	int c[maxn];

	inline int lowbit(int x){

		return x&(-x);

	}

	int ask(int x){

		int ans=0;

		for(;x;x-=lowbit(x))ans+=c[x];

		return ans;

	}

	void add(int x,int y){

		for(;x<=n;x+=lowbit(x))c[x]+=y;

	}

	void clear(int x){

		for(;x<=n;x+=lowbit(x)){

			if(c[x])c[x]=0;

			else break;

		}

	}

}

void cdq(int L,int R){

	if(R==L)return;

	int M=(L+R)>>1;

	cdq(L,M);

	cdq(M+1,R);

	int l=L,r=M+1;

	int o=L;

	while(l<=M&&r<=R){

		if(query[l]<query[r]){

			if(query[l].type==0)

				BIT::add(query[l].y,query[l].cnt);

			tmp[o++]=query[l++];

		}

		else{

			if(query[r].type==1)

				ans[query[r].num]+=query[r].flag*BIT::ask(query[r].y);

			tmp[o++]=query[r++];

		}

	}

	while(l<=M)

		tmp[o++]=query[l++];

	while(r<=R){

		if(query[r].type==1)

			ans[query[r].num]+=query[r].flag*BIT::ask(query[r].y);

		tmp[o++]=query[r++];

	}

	for(int i=L;i<=R;i++){

		BIT::clear(tmp[i].y);

		query[i]=tmp[i];

	}

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		p[a[i]]=i;

	}

	for(int i=1;i<=n;i++){

		scanf("%d",&b[i]);

		mp[i]=p[b[i]];

		query[++tot]=(Query){0,i,mp[i],0,0,1};

	}

	int cnt=0;

	for(int i=1;i<=m;i++){

		int flag;

		scanf("%d",&flag);

		if(flag==1){

			cnt++;

			int l1,r1,l2,r2;

			scanf("%d%d%d%d",&l2,&r2,&l1,&r1);

			query[++tot]=(Query){1,l1-1,l2-1,1,cnt,1};

			query[++tot]=(Query){1,l1-1,r2,-1,cnt,1};

			query[++tot]=(Query){1,r1,l2-1,-1,cnt,1};

			query[++tot]=(Query){1,r1,r2,1,cnt,1};

		}

		else{

			int x,y;

			scanf("%d%d",&x,&y);

			query[++tot]=(Query){0,x,mp[x],0,0,-1};

			query[++tot]=(Query){0,y,mp[y],0,0,-1};

			swap(mp[x],mp[y]);

		 	query[++tot]=(Query){0,x,mp[x],0,0,1};

			query[++tot]=(Query){0,y,mp[y],0,0,1};

		}

	}

	cdq(1,tot);

	for(int i=1;i<=cnt;i++)

		printf("%d\n",ans[i]);

}

//2 3

//1 2

//2 1

//1 1 1 1 1

//2 1 2

//1 1 1 1 1

---恢复内容结束---

巴特西

Codeforces 1093E Intersection of Permutations (CDQ分治+树状数组）

最新文章

热门文章