[CF1093E]Intersection of Permutations

题目大意：

给定两个长度为\(n(n\le2\times10^5)\)的排列\(A,B\)。\(m(m\le2\times10^5)\)次操作，操作分为以下两种：

询问有多少同时在\(A_{[x,y]}\)和\(B_{[l,r]}\)中出现的数。
交换\(B_x\)与\(B_y\)。

思路：

令\(v[a[i]]=i,b[i]=v[b[i]]\)，这样询问就变成\([x,y]\)中有多少数在\(B_{[l,r]}\)中出现。

用树状数组+平衡树维护每个区间出现哪些数，询问时在平衡树中查找排名即可。

源代码：

#include<cstdio>

#include<cctype>

#include<climits>

#include<ext/pb_ds/tree_policy.hpp>

#include<ext/pb_ds/assoc_container.hpp>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=2e5+1;

int n,v[N],a[N];

using namespace __gnu_pbds;

using RBTree=tree<int,null_type,std::less<int>,rb_tree_tag,tree_order_statistics_node_update>;

class FenwickTree {

	private:

		RBTree t[N];

		int lowbit(const int &x) const {

			return x&-x;

		}

		int query(int p,const int &x,const int &y) const {

			int ret=0;

			for(;p;p-=lowbit(p)) {

				const int L=*t[p].lower_bound(x);

				const int R=*std::prev(t[p].upper_bound(y));

				if(L<=R) ret+=t[p].order_of_key(R)-t[p].order_of_key(L)+1;

			}

			return ret;

		}

	public:

		void init() {

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

				t[i].insert(INT_MIN);

				t[i].insert(INT_MAX);

			}

		}

		void insert(int p,const int &x) {

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

				t[p].insert(x);

			}

		}

		void erase(int p,const int &x) {

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

				t[p].erase(x);

			}

		}

		int query(const int &l,const int &r,const int &x,const int &y) const {

			return query(r,x,y)-query(l-1,x,y);

		}

};

FenwickTree t;

int main() {

	n=getint();

	const int m=getint();

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

		v[getint()]=i;

	}

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

		a[i]=v[getint()];

	}

	t.init();

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

		t.insert(i,a[i]);

	}

	for(register int i=0;i<m;i++) {

		const int opt=getint(),x=getint(),y=getint();

		if(opt==1) {

			const int l=getint(),r=getint();

			printf("%d\n",t.query(l,r,x,y));

		}

		if(opt==2) {

			t.erase(x,a[x]);

			t.erase(y,a[y]);

			std::swap(a[x],a[y]);

			t.insert(x,a[x]);

			t.insert(y,a[y]);

		}

	}

	return 0;

}

巴特西

[CF1093E]Intersection of Permutations

[CF1093E]Intersection of Permutations

题目大意：

思路：

源代码：

最新文章

热门文章