先补点知识： 异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。 简单理解就是不进位加法，如1+1=0，,0+0=0,1+0=1。 性质 1、交换律 2、结合律（即(a^b)^c == a^(b^c)） 3、对于任何数x，都有x^x=0，x^0=x 4、自反性 A XOR B XOR B = A xor 0 = A 所以求[l,r]中出现偶数的数字的异或值，那么我们可以先将[l,r]中的数字全部异或起来然后再异或[l,r]中所有不重复数字的异或值。 比如说[l,r]中的数字是1,3,9,3 首先1^3^9^3,然后得到的结果（1^3^9^3）^(1^3^9) 显然，将[l,r]中的数字全部异或很容易，弄一个前缀异或和num[i],那么[l,r]全部数字的异或和=num[r]^num[l-1], 现在就只需求出[l,r]中所有不重复数字的异或值。 这就需要一点技巧，将询问按r值排序，D记录每个数前一次出现的位置。 走到i时，如果a[i]出现过，那么把他上次出现的位置异或掉，再在i位置上异或上a[i]。 用树状数组维护区间异或和。
#include <iostream> #include <stdio.h> #include <algorithm> #include <stdlib.h> #include <stack> #include <vector> #include <string.h> #include <queue> #define msc(X) memset(X,-1,sizeof(X)) #define ms(X) memset(X,0,sizeof(X)) typedef long long LL; using namespace std; const int MAXN=1000009; int t[MAXN],a[MAXN],num[MAXN],n,q;; struct _Node { int id,l,r; bool operator < (const _Node &a) const{ return r<a.r; } }node[MAXN]; int C[MAXN],D[MAXN]; void add(int x,int val) { while(x<=n){ C[x]^=val; x+=x&-x; } } int sum(int x) { int rt=0; while(x>0){ rt^=C[x]; x-=x&-x; } return rt; } int ans[MAXN]; int main(int argc, char const *argv[]) { ms(C); ms(D); scanf("%d",&n); num[0]=0; for(int i=1;i<=n;i++)//哈希 { scanf("%d",a+i); t[i]=a[i]; num[i]=num[i-1]^a[i]; } sort(t+1,t+n+1); int m=unique(t+1,t+n+1)-t-1; for(int i=1;i<=n;i++) { int pos=lower_bound(t+1,t+m+1,a[i])-t; a[i]=pos; } scanf("%d",&q); for(int i=1;i<=q;i++) { node[i].id=i; scanf("%d %d",&node[i].l,&node[i].r); } sort(node+1,node+q+1); int pos=1; for(int i=1;i<=q;i++) { while(pos<=node[i].r){ if(D[a[pos]]) add(D[a[pos]],t[a[pos]]); add(pos,t[a[pos]]); D[a[pos]]=pos; ++pos; } ans[node[i].id]=num[node[i].r]^ num[node[i].l-1]^sum(node[i].r)^sum(node[i].l-1); } for(int i=1;i<=q;i++) printf("%d\n",ans[i] ); return 0; }