AtCoder Beginner Contest 185, F : Range Xor Query

問題文

　https://atcoder.jp/contests/abc185/tasks/abc185_f

問題概要

　長さ $N$ の正整数の列 $A$ について，以下の 2 種類のクエリが $Q$ 個飛んでくる．順に処理せよ．

• クエリ 1 : $A_{ X_i }$ を $A_{ X_i } \oplus Y_i$ で置き換える
• クエリ 2 : $\oplus_{ i = X_i }^{ Y_i } A_i$ を出力する

なお，記号 $\oplus$ は bitwise XOR の二項演算を表す．

制約

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 3 \times 10^5$
• $0 \leq A_i \leq 2^{ 30 }$
• $X_i, Y_i$ に関するいい感じの制約（意味的に破綻しない）

解法

　やや天下り的ですが，$\oplus$ は $0$ を単位元としてもち，結合則が成り立ちます．よって，いわゆる Segment Tree に載せることができます．Segment Tree の詳細については蟻本など [1][2] に任せます．
　問題を解くという観点で言えば，Segment Tree は ACL にあるので，これを利用することもできます．複合代入のようなものは直接的にはサポートされていませんが，一旦 get してから XOR を計算して改めて set することでエミュレートできます．

参考文献

[1] 秋葉拓哉, 岩田陽一, & 北川宜稔. (2010). プログラミングコンテストチャレンジブック.
[2] プログラミングコンテストでのデータ構造 - SlideShare

コード

#include <atcoder/segtree>
using namespace atcoder;

int op( const int a, const int b )
{
	return a ^ b;
}

int e()
{
	return 0;
}

int main()
{
	IN( int, N, Q );
	VI A( N );
	cin >> A;

	segtree< int, op, e > seg( A );
	REP( Q )
	{
		IN( int, T, X, Y );
		--X;

		if ( T == 1 )
		{
			const int a = seg.get( X );
			seg.set( X, a ^ Y );
		}
		else
		{
			cout << seg.prod( X, Y ) << '\n';
		}
	}

	cout << flush;

	return 0;
}