Description
给你n( 1<=n<=1000000)个数,以及m(1<=m<=1000000)个询问,每个询问包括l和r，问你在这n个数中，区间l~r，出现偶数个数的数的异或和
Input
第一行一个整数 n，表示数列的长度
接下来一行 n 个非负整数，表示 a 数组中的每个元素
接下来一行一个整数 m，表示查询的数量
接下来 m 行，每行两个整数 l, r 表示这次查询区间的左右端点
Output
对于每组查询，输出一行一个整数，表示这组查询的答案
刚看到题的一瞬间,输出出现偶数次的数的异或和.
"不是0嘛？这不sb题？"
突然发现看错题.
原来是求出现偶数次的单个数的异或和。
通过一些推导可以发现,答案是求区间内不同数的异或和与区间异或和的异或和。
为什么？
我们假设当前查询的区间的数为：\(1,3,4,2,5,4,1\)
此时根据异或的性质\(x\) ^\(x=0\),我们再异或上区间内不同的数。
则这段异或起来就是：\(1\)^\(4\)。
稍作解释一下
我们区间中出现偶数次的数的异或和就是\(0\)，此时再异或上区间内不同的数。
此时这些出现偶数次的数的异或再次出现。
而那些出现单次的数就消失了.
那么现在问题就变为维护区间内不同的数的异或和
这题数据范围的话,需要离散化。
因为没有修改操作,所以考虑离线.我们对右端点进行排序(从小到大)
然后考虑用一种数据结构维护：线段树 or 树状数组。
这里用了树状数组。
树状数组维护异或。
记录一下这个数上一个出现的位置.
然后遇到某个位置再出现,我们再在树状数组删去这个数几个(即再异或一次.)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register
using namespace std;
const int gz=3000008;
inline void in(R int &x)
{
R int f=1;x=0;R char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,a[gz],sum[gz],pre[gz],b[gz],head[gz];
int new_n=1,q,ans[gz];
struct cod
{
int l,r,idx;
bool operator <(const cod&a)const
{
return r<a.r;
}
}que[gz];
#define lowbit(x) x&-x
int tr[gz<<1];
inline void add(R int o,R int del)
{
for(;o<=n;o+=lowbit(o))
tr[o]^=del;
}
inline int query(R int o)
{
R int res=0;
for(;o;o-=lowbit(o))
res^=tr[o];
return res;
}
int main()
{
in(n);
for(R int i=1;i<=n;i++)in(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
for(R int i=2;i<=n;i++)
if(b[new_n]!=b[i])b[++new_n]=b[i];
for(R int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+new_n+1,a[i])-b;
for(R int i=1;i<=n;i++)
{
sum[i]=sum[i-1]^b[a[i]];
pre[i]=head[a[i]];
head[a[i]]=i;
}
in(q);
for(R int i=1;i<=q;i++)
in(que[i].l),in(que[i].r),que[i].idx=i;
sort(que+1,que+q+1);
R int now=1;
for(R int i=1;i<=q;i++)
{
R int r=que[i].r,l=que[i].l;
while(now<=r)
{
if(pre[now])
add(pre[now],b[a[now]]);
add(now,b[a[now]]);
now++;
}
ans[que[i].idx]=(query(r)^query(l-1))^(sum[r]^sum[l-1]);
}
for(R int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}