CPSCO2019 Session1 E - Exclusive OR Queries (500)

E - Exclusive OR Queries

概要

長さNの数列Aがある。Q個のクエリが与えられるので、それに解答せよ。

• i番目のクエリではLi, Ri, Xiが与えられる。AのうちLi以上Ri以下のすべての項のXORを答えよ。またその後、Li以上Ri以下のすべての項をXiにする。

制約

1 ≦ N ≦ 3 * 10^5
1 ≦ Q ≦ 2 * 10^5
0 ≦ Ai, Li, Ri, Xi ≦ 10^9

方針

multisetを使う。

「Li以上Ri以下のすべての項のXORを答える」ところは
multiset.lower_bound(Li)を使ってLi以上の最小の項を特定し、一つずつイテレータを動かして愚直に実行する。
このときXORをとった項はすべてmultisetから除外する。

その後、「Li以上Ri以下のすべての項をXiにする」ところを実行してゆく。
XORの性質から、同じ数字の奇数個のXORはその数字自身になり、偶数個のXORは0になる。
よって除外した数字の個数をカウントし、そのカウンタが奇数ならXiをmultisetにinsertする。

計算量の見積もりが重要で、全クエリを通して除外されるのは高々N+Q個、追加されるのは高々Q個であるので、全クエリを通して除外と追加に係る計算量はO(N+Q)となり、間に合う。

解答

Submission #5325092 - CPSCO2019 Session1

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, Q;
	cin >> N >> Q;
 
	multiset<int> ms;
	rep(i, N){
		int a;
		cin >> a;
		ms.insert(a);
	}
 
	rep(i, Q){
		int L, R, X;
		cin >> L >> R >> X;
 
		auto it = ms.lower_bound(L);
		int ans = 0;
		int cnt = 0;
		while(it != ms.end()){
			if(*it <= R){
				ans ^= *it;
				it = ms.erase(it);
				cnt++;
			}else{
				break;
			}
		}
 
		cout << ans << endl;
		if(cnt % 2 == 1) ms.insert(X);
	}
}