题解 CF703D 【Mishka and Interesting sum】
顾z
2018-11-02 20:07:40
刚看到题的一瞬间,输出出现偶数次的数的异或和.
~~"不是0嘛？这不sb题？"~~
突然发现看错题.
原来是求**出现偶数次的单个数的异或和**。
通过一些推导可以发现,答案是**求区间内不同数的异或和与区间异或和的异或和**。
为什么？
我们假设当前查询的区间的数为：$1,3,4,2,5,4,1$
此时根据异或的性质$x$ ^$x=0$,我们再异或上区间内不同的数。
则这段异或起来就是：$1$^$4$。
稍作解释一下
> 我们区间中出现偶数次的数的异或和就是$0$，此时再异或上区间内不同的数。
>
> 此时这些出现偶数次的数的异或再次出现。
>
> 而那些出现单次的数就消失了.
那么现在问题就变为**维护区间内不同的数的异或和**
这题数据范围的话,需要**离散化**。
因为没有修改操作,所以考虑离线.我们对右端点进行排序(**从小到大**)
然后考虑用一种数据结构维护：线段树 or 树状数组。
这里用了**树状数组**。
**树状数组维护异或**。
记录一下这个数上一个出现的位置.
然后遇到某个位置再出现,我们再在树状数组删去这个数几个(即再异或一次.)
``代码``
```c++
#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;
}
```