Codeforces #197 Div2. D. Xenia and Bit Operations

これはDiv2でもB～Cで出てもいい問題だな…。
http://codeforces.com/contest/339/problem/D

問題

2^N要素からなる数列Aが与えられる。
数列Aに対し、奇数ステップ目では隣同士の要素のorを取った要素数半分の数列を作る。
偶数ステップ目では隣同士の要素のxorを取った要素数半分の数列を作る。
上記処理を数列の要素数が1になるまで繰り返し、その時の値を数列Aの計算値と呼ぶことにする。

ここで、M回数値p,mが与えられ、A[p]=mと数列の1要素が変更される。
各変更に対して数列Aの計算値を再計算せよ。

解法

SegTreeそのまま。
2^N要素からなるN段の二分木を作ってor/xorの途中計算結果を保持しておき、要素が更新されるたびに木の葉から根まで再計算すればよい。
O(MN)で完了する。

int N,M;
int A[18][1000001];

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N>>M;
	FOR(i,1<<N) cin>>A[0][i];
	FOR(i,N) FOR(j,1<<(N-1-i)) A[i+1][j] = (i%2)?(A[i][j*2]^A[i][j*2+1]):(A[i][j*2]|A[i][j*2+1]);
	
	FOR(i,M) {
		cin>>x>>y;
		x--;
		A[0][x]=y;
		FOR(j,N) A[j+1][x/2]=(j%2)?(A[j][x]^A[j][x^1]):(A[j][x]|A[j][x^1]),x/=2;
		_P("%d\n",A[N][0]);
	}
}

まとめ

えらいそのまんまの問題が出たもんだ。