CPSCO2019 Session1 : E - Exclusive OR Queries

初日は本番参加してないけど自力全完できた。
https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_e

問題

N要素の整数列が与えられる。
以下のQ個のクエリに順次答えよ。

区間[L,R]と整数Xが与えられる。
数列中この範囲に収まる値のxorを答えよ。
その後、この範囲に収まる値をXに置き換えよ。

解法

同じ値が複数個あった場合、それらが区間に収まるかどうかは常に条件が同じで、かつ区間に収まる場合はxorを取るので同じ値は偶奇だけ気にすればよい。
もっと言うと、偶数ならなかったものとしてみなしてよく、0か1かだけ考えればよい。

元の数列をsetで管理するとする。
[L,R]の範囲の値をすべて取り出して、Xを追加か削除するので、均しでsetの操作回数はO(N+Q)で済む。

int N,Q;
set<int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		if(M.count(x)) M.erase(x);
		else M.insert(x);
	}
	
	FOR(i,Q) {
		int num=0,ret=0;
		int L,R,X;
		cin>>L>>R>>X;
		while(1) {
			auto it=M.lower_bound(L);
			if(it==M.end()||*it>R) break;
			num^=1;
			ret^=*it;
			M.erase(it);
		}
		
		cout<<ret<<endl;
		if(num) {
			if(M.count(X)) M.erase(X);
			else M.insert(X);
		}
	}
	
	
}

まとめ

これは500ptとしても簡単な方だね。