Codeforces #365 Div2 D. Mishka and Interesting sum

ちょっと迷ったけどどうにかなった。
http://codeforces.com/contest/703/problem/D

問題

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

各クエリは２値(L,R)で構成される。
A[L...R]の範囲に登場する数値で、２回以上偶数回登場した要素について、それらのxorを取った値を求めよ。
(xorを取るのは対象の要素について2,4,6,...回と何度登場したとしても１回ずつ)

解法

まずクエリをR順に分類しておく。
A[i]をiの昇順に処理していき、その際Rがiとなるクエリをそのつど処理していく。
その際SegTreeやBITを用いることができる。

A[i]を処理していくとき、A[i]が２回目以上登場したとする。
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]);
}

まとめ

意外とコードは短い。