Codeforces 339D Xenia and Bit Operations

問題

長さが2^nの配列が与えられる。
配列に対する値vを以下のように計算する。
(a[0] or a[1]), (a[2] or a[3]), (a[4] or a[5]) ...を新たな数列aとする
(a[0] xor a[1]), (a[2] xor a[3]), (a[4] xor a[5]) ...を新たな数列aとする
というように、隣接する項をペアにして、or xor or xor...としていく操作を、項が1個になるまで繰り返す。
vをそのときのa[0]とする。
（ただしor, xorはビット毎のor, xorである）

クエリがm個来る。
クエリはaのp番目の項をqにする操作である。
各クエリが終わった時点でのvの値をそれぞれ出力せよ。

制約条件

n≦17
m≦100000
a[i]＜2^30

方針

適当にsegtreeを更新するだけ。
一回の操作はO(log(2^n))で、m回クエリが来るので、計算量はO(nm)

自分は誤読のときの名残でbitを30回にわけて操作をしているが、別にまとめてやればいい。

ソースコード

int n, m, a[1 << 17], b[1 << 18];
int p[100000], q[100000], ans[100000];

int main(){
	scanf("%d%d", &n, &m);
	rep(i, 1 << n) scanf("%d", a + i);
	rep(i, m) scanf("%d%d", p+i, q+i), p[i]--;
	
	rep(bit, 30){
		int N = (1 << n) - 1;
		rep(i, 1 << n) b[i + N] = a[i] >> bit & 1;
		rep(i, n){
			N -= 1 << n-1-i;
			for(int j = N; j < N + (1<<n-1-i); j++)
			b[j] = i % 2 ? b[j*2+1] ^ b[j*2+2]
				: b[j*2+1] | b[j*2+2];
		}
		assert(N == 0);
		
		rep(i, m){
			int pos = p[i] + (1 << n) - 1, v = q[i] >> bit & 1;
			b[pos] = v;
			
			rep(j, n){
				int pp = (pos-1) / 2;
				int x = b[pp*2+1], y = b[pp*2+2];
				
				b[pp] = j % 2 ? x ^ y : x | y;
				pos = pp;
			}
			ans[i] |= b[0] << bit;
		}
	}
	rep(i, m) printf("%d\n", ans[i]);
	
	return 0;
}