树状数组,与Turing Tree类似。
xr[i]表示从1到i的抑或,树状数组维护从1到i每个数只考虑一次的异或,结果为sum(r) ^ sum(l) ^ xr[r] ^ xr[l]
其中xr[r] ^ xr[l] 相当于l + 1到r出现奇数次的数的异或,sum(r) ^ sum(l)表示l + 1到r每个数只考虑一次的异或,则两者异或为出现偶数次的数的异或。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
const int N = 1000008, INF = 0x3F3F3F3F;
#define MS(a, num) memset(a, num, sizeof(a))
#define PB(A) push_back(A)
#define FOR(i, n) for(int i = 0; i < n; i++)
int a[N];
struct Que{
int l, r, i;
}que[N];
int C[N],n;
int ans[N];
int xr[N];
inline int lowbit(int x){
return x&-x;
}
void add(int x, int val){
for(int i=x;i<=n;i+=lowbit(i)){
C[i] ^= val;
}
}
int sum(int x){
int ret = 0;
for(int i=x;i>0;i-=lowbit(i)){
ret^=C[i];
}
return ret;
} bool cmp(const Que &a, const Que &b){
return a.r < b.r;
}
int main(){
int t, q;
scanf("%d", &n);
xr[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
xr[i] = xr[i - 1] ^a[i];
}
scanf("%d", &q);
for(int i = 0; i < q; i++){
scanf("%d %d", &que[i].l , &que[i].r);
que[i].i = i;
}
sort(que, que + q, cmp);
MS(C, 0 );
map<int, int> vis;
int j = 0;
for(int i = 1; i <= n; i++){
if(vis.find(a[i]) != vis.end()){
int p = vis[a[i]];
add(p, a[i]);
}
vis[a[i]] = i;
add(i, a[i]);
while(j < q && que[j].r == i){
int l = que[j].l - 1, r = que[j].r;
ans[que[j].i] = sum(r) ^ sum(l) ^ xr[r] ^ xr[l];
j++;
}
}
for(int i = 0; i < q; i++){
printf("%d\n", ans[i]);
}
return 0;
}