Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum
http://codeforces.com/contest/703/problem/D
解法
even ではなく odd であれば普通に区間の和を取れば求まる。
(even の和)=(distinct な和)xor (odd の和)なので、distinct な和を求めることができれば解くことができる。
distinct な和を求めるには、クエリを先読みして次のような処理をする。
pos[10^6] = {-1, -1, -1, ... }; for (int i = 0; i < n; i++) { if (pos[a[i]] != -1) { bit.update(pos[a[i]], a[i]); } pos[a[i]] = i; bit.update(pos[a[i]], a[i]); for (int qid : 右端が i であるクエリの集合) { ans[qid] = bit.query(r[qid]) ^ bit.query(l[qid] - 1); } }
i 以前に現れた v のうち、最も右にある v だけを BIT に入れておく、という処理をしている。
値をできるだけ右に寄せておけばうまくヒットするので、これでうまくいく。
割とよく使うテクで、実は 2 回解説で書いたことがある。