kmjp's blog

競技プログラミング参加記です

Codeforces ECR #056 : E. Intersection of Permutations

平方分割で通るのか…。
https://codeforces.com/contest/1093/problem/E

問題

1~NのPermutationとなる、2つの数列A,Bが与えられる。
以下のクエリに答えよ。

  • 2つの区間[La,Ra]、[Lb,Rb]が指定されるので、A[La...Ra]とB[Lb...Rb]両方に含まれる要素数を答えよ。
  • 指定されたBの2要素をswapする。

解法

数列の数字に具体的な意味はないので、Aが1~Nと昇順となるように数字を付け替えよう。
そうするとB[Lb...Rb]の間に[La...Ra]の範囲の数字が何個あるかを答える問題になる。

これは平方分割で解くことができる。
BをD=√N個のBucketに分け、それぞれBITを作ろう。
各BIT内には、1~Nの登場頻度0/1を書くようにする。

そうすると前者のクエリはBITをO(D)個と、Bucket境界に合わないO(D)を辿ることで[La,Ra]の範囲の数字の登場回数を求められる。

int N,M;
int A[202020];
int B[302020];
const int DI=1000;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,18> bt[400];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) {
		scanf("%d",&x);
		A[x]=i;
	}
	FOR(i,N) {
		scanf("%d",&x);
		B[i]=A[x];
		bt[i/DI].add(B[i],1);
	}
	
	
	while(M--) {
		scanf("%d",&i);
		if(i==1) {
			int LA,RA,LB,RB;
			scanf("%d%d%d%d",&LA,&RA,&LB,&RB);
			LA--;
			RA--;
			LB--;
			int num=0;
			while(LB<RB && LB%DI) {
				if(B[LB]>=LA && B[LB]<=RA) num++;
				LB++;
			}
			while(LB<RB && RB%DI) {
				RB--;
				if(B[RB]>=LA && B[RB]<=RA) num++;
			}
			while(LB<RB) {
				num+=bt[LB/DI](RA)-bt[LB/DI](LA-1);
				LB+=DI;
			}
			cout<<num<<endl;
			
		}
		else {
			scanf("%d%d",&x,&y);
			x--,y--;
			bt[x/DI].add(B[x],-1);
			bt[y/DI].add(B[y],-1);
			swap(B[x],B[y]);
			bt[x/DI].add(B[x],1);
			bt[y/DI].add(B[y],1);
		}
	}
}

まとめ

BITでなくソート済み配列のlower_boundだと間に合わなかった。