ちょっと迷ったけどどうにかなった。
http://codeforces.com/contest/703/problem/D
問題
N要素の整数列A[i]が与えられる。
以下のクエリQ個に答えよ。
各クエリは2値(L,R)で構成される。
A[L...R]の範囲に登場する数値で、2回以上偶数回登場した要素について、それらのxorを取った値を求めよ。
(xorを取るのは対象の要素について2,4,6,...回と何度登場したとしても1回ずつ)
解法
まずクエリをR順に分類しておく。
A[i]をiの昇順に処理していき、その際Rがiとなるクエリをそのつど処理していく。
その際SegTreeやBITを用いることができる。
A[i]を処理していくとき、A[i]が2回目以上登場したとする。
A[i]が登場したindexが...e,f,g,h,iとする。
Lが[e+1,f]や[g+1,h]である場合、A[L...R]中にA[i]が偶数回現れる。
そこで、A[i]が直前に登場したindex hを覚えておき、SegTreeなりBIT上で区間[0,h]にA[i]をxorで足しこんでいく、という処理を行えばよい。
このSegTreeなりBITのL番目の要素を取れば、それがクエリ(L,R)の回。
template<class V, int ME> class BIT { public: V bit[1<<ME],val[1<<ME]; V total(int e) {V s=0;e++;while(e) s^=bit[e-1],e-=e&-e; return s;} V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]^=v,e+=e&-e;} }; int N,M; int A[1010101],X[1010101]; int L[1010101],R[1010101],ret[1010101]; vector<int> RR[1010101]; map<int,int> pre; BIT<int,21> bt; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d",&N); FOR(i,N) scanf("%d",&A[i+1]); scanf("%d",&M); FOR(i,M) { scanf("%d%d",&L[i],&R[i]); RR[R[i]].push_back(i); } int T=0; for(i=1;i<=N;i++) { if(pre.count(A[i])) { bt.add(1,A[i]); bt.add(pre[A[i]]+1,A[i]); } pre[A[i]]=i; FORR(r,RR[i]) ret[r]=bt.total(L[r]); } FOR(i,M) _P("%d\n",ret[i]); }
まとめ
意外とコードは短い。