AtCoder ABC #185 : F - Range Xor Query

こちらも典型。
https://atcoder.jp/contests/abc185/tasks/abc185_f

問題

数列Aが与えられる。
以下のクエリに順次答えよ。

• 1つの値A[x]をA[x] xor yで置き換える
• A[x]～A[y]のxorを取った値を返す

解法

BITで累積和を取る際、xorを演算子として利用すればよい。

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,20> bt;

int N,Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		bt.add(i+1,x);
	}
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			bt.add(x,y);
		}
		else {
			cout<<(bt(y)^bt(x-1))<<endl;
		}
	}
}

まとめ

うーむ。