Codeforces ECR #035 : G. Mass Change Queries

またしょうもないミスで落とす…。
http://codeforces.com/contest/911/problem/G

問題

N要素の数列Aが与えられる。
ここにQ個のクエリを適用する。
各クエリはL,R,X,Yの４値で構成される。
これはi∈[L,R]のうちA[i]=Xであるものについて、A[i]=Yにすることを意味する。

全クエリ処理後のAの値を答えよ。

解法

値の変更を遅延伝搬SegTreeで反映させるのが想定解っぽい。
ただし、これはビット演算でゴリ押ししてO(NQ/|w|)でも間に合う。

Aのうち値がvであるような要素を示すbitset B[v]を考えよう。
各クエリについて、B[X]の一部分を抽出してB[Y]にorで足しこんで元のB[X]を空にする、を繰り返せばよい。
X==Yの場合だけ注意。

int N;
ll B[101][3200];
int Q;
int L,R,X,Y;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d",&	x);
		B[x][i>>6] |= 1LL<<(i&63);
	}
	scanf("%d",&Q);
	FOR(i,Q) {
		scanf("%d%d%d%d",&L,&R,&X,&Y);
		L--;
		if(X==Y) continue;
		while((L&63) && (L<R)) {
			B[Y][L>>6] |= B[X][L>>6] & (1LL<<(L&63));
			B[X][L>>6] ^= B[X][L>>6] & (1LL<<(L&63));
			L++;
		}
		while(L+64<=R) {
			B[Y][L>>6] |=B[X][L>>6];
			B[X][L>>6]=0;
			L+=64;
		}
		while(L<R) {
			B[Y][L>>6] |= B[X][L>>6] & (1LL<<(L&63));
			B[X][L>>6] ^= B[X][L>>6] & (1LL<<(L&63));
			L++;
		}
	}
	FOR(i,N) {
		FOR(x,101) if(B[x][i>>6] & (1LL<<(i&63))) break;
		_P("%d%c",x,(i==N-1)?'\n':' ');
	}
	
}

まとめ

せっかくすんなり解法にたどり着いたのに、しょうもないミスするのもったいないな。