题目链接：http://codeforces.com/contest/703/problem/D
给你n个数，m次查询，每次查询问你l到r之间出现偶数次的数字xor和是多少。
我们可以先预处理前缀和Xor[i]，表示1~i的xor和。因为num^num=0，所以Xor[r] ^ Xor[l - 1]求的是l~r之间出现奇数次的数字xor和。
那怎么求偶数次的呢，那我们可以先求l到r之间不重复出现数字的xor（比如1 1 2 求的是1 ^ 2），然后再xor以上求出的Xor[r] ^ Xor[l - 1]，奇奇消掉 就得出答案了。
那求不重复的话，我们用树状数组来处理。先把询问按照r从小到大排序，以便后面的离线处理。map存的是a[i]数字最近出现的位置i，然后用树状数组i位置插入a[i]并且消掉a[i]之前出现的位置i'，这样保证查询不重复xor和最优。
具体看代码，应该能看懂。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e6 + ;
int bit[N], Xor[N], a[N], ans[N], n;
map <int, int> mp; //a[i]最近出现的位置
struct Query {
int l, r, id;
bool operator <(const Query& cmp) const {
return r < cmp.r;
}
}q[N]; void update(int i, int val) {
for(; i <= n; i += (i&-i))
bit[i] ^= val;
} int sum(int i) {
int s = ;
for(; i >= ; i -= (i&-i))
s ^= bit[i];
return s;
} int main()
{
int m;
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
scanf("%d", a + i);
Xor[i] = Xor[i - ] ^ a[i]; //前缀xor
}
scanf("%d", &m);
for(int i = ; i <= m; ++i) {
scanf("%d %d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q + , q + m + );
int j = ; //询问的结构体下标
for(int i = ; i <= n; ++i) {
int &temp = mp[a[i]]; //引用
if(temp) { //要是不是第一次出现，那就消掉a[i]之前出现的位置
update(temp, a[i]);
}
temp = i;
update(temp, a[i]); //插入最近的位置
while(j <= m && i == q[j].r) {
int l = q[j].l - , r = q[j].r;
ans[q[j].id] = sum(r) ^ sum(l) ^ Xor[r] ^ Xor[l];
++j;
}
}
for(int i = ; i <= m; ++i) {
printf("%d\n", ans[i]);
}
return ;
}
上面是正确的代码，下面是TLE的。
之前用莫队写的，数据小一点应该可以过。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int MAXN = 1e6 + ;
typedef __int64 LL;
int a[MAXN] , u, ans[MAXN];
struct que {
int l , r , id;
}q[MAXN];
map <int, int> mp; bool cmp(que x , que y) {
if(x.l / u == y.l / u)
return x.r < y.r;
return x.l / u < y.l / u;
} int main()
{
int n , m;
while(~scanf("%d" , &n)) {
for(int i = ; i <= n ; i++) {
scanf("%d" , a + i);
}
scanf("%d", &m);
for(int i = ; i <= m ; i++) {
scanf("%d %d" , &q[i].l , &q[i].r);
q[i].id = i;
}
u = (int)sqrt(n*1.0);
sort(q + , q + m + , cmp);
int L = , R = , num;
int temp = ;
for(int i = ; i <= m ; i++) {
while(R > q[i].r) {
num = --mp[a[R]];
if(num) {
temp ^= a[R];
}
R--;
}
while(R < q[i].r) {
R++;
num = ++mp[a[R]];
if(num > ) {
temp ^= a[R];
}
}
while(L < q[i].l) {
num = --mp[a[L]];
if(num) {
temp ^= a[L];
}
L++;
}
while(L > q[i].l) { //前面的还没算
L--;
num = ++mp[a[L]];
if(num > ) {
temp ^= a[L];
}
}
ans[q[i].id] = temp;
}
for(int i = ; i <= m ; i++) {
printf("%d\n", ans[i]);
}
}
return ;
}