Codeforces #364 D. Mishka and Interesting sum

正文索引 [隐藏]

传送门:http://www.codeforces.com/contest/703/problem/D

题目翻译

一个长度为N的序列,m个询问,问[l,r]区间内出现偶数次的数字的Xor和。

题解

我们可以离线所有询问(不离线可以用主席树一样的方法搞,然而这里N=1e6空间开不下)
我们首先对序列做个Xor前缀和
所有询问按右端点排序
然后对于一个询问[l,r],我们使用一个树状数组,每个不同的数字,我们只在区间内他最右边的位置统计它。
然后直接询问树状数组上[l,r]之间的Xor和,就是所有不同数字的Xor和,然后在Xor上这段区间的Xor和,就是出现偶数次数字的Xor和了。

代码