Codeforces 703D Mishka and Interesting sum(树状数组+扫描线)

时间:2021-10-03 16:43:26

【题目链接】 http://codeforces.com/contest/703/problem/D

【题目大意】

  给出一个数列以及m个询问,每个询问要求求出【L,R】区间内出现次数为偶数的数的异或和。

【题解】

  显然,我们很容易求出区间内出现次数为奇数的数的异或和,那么如果我们可以求出区间内出现的所有数的异或和,那么将两者异或就可以得到要求的东西。

  我们记一个数字上一次出现的位置为pre,对于【L,R】中的数,如果其pre是小于L的,那么它肯定是第一次在这个区间出现,所以现在问题就转化为求【L,R】区间内所有pre小于L的数的异或和。

  将【L,R】区间的查询拆分为L-1位置对L-1前缀的查询,R位置对L-1前缀,拆分后的查询仅和数列处理到的位置有关,因此考虑扫描线,以pre为下标,在树状数组中维护异或和,对拆分后的查询进行线扫描,依次处理答案。

【代码】

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int N=1000005;
map<int,int> t;
int f[N],m,n,c[N],a[N],pre[N],x[N],y[N],ans[N],tmp=0,sum[N];
int add(int x,int num){while(x<N)c[x]^=num,x+=x&-x;}
int query(int x){int s=0;while(x>0)s^=c[x],x-=x&-x;return s;}
struct data{int q,s,id,ans;}p[N*2];
bool cmp(data a,data b){return a.s<b.s;}
bool cmp0(data a,data b){return a.id<b.id;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]^a[i];
pre[i]=t[a[i]];
t[a[i]]=i;
}scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x[i],&y[i]);
p[i*2-1].q=x[i]-1;p[i*2].q=x[i]-1;
p[i*2-1].s=x[i]-1;p[i*2].s=y[i];
p[i*2-1].id=i*2-1;
p[i*2].id=i*2;
}int cnt=1;
sort(p+1,p+2*m+1,cmp);
while(p[cnt].s==0)cnt++;
for(int i=1;i<=n;i++){
add(pre[i]+1,a[i]);
while(p[cnt].s==i){
p[cnt].ans=query(p[cnt].q+1);
cnt++;if(cnt>2*m)break;
}
}sort(p+1,p+2*m+1,cmp0);
for(int i=1;i<=m;i++)printf("%d\n",p[2*i].ans^p[2*i-1].ans^sum[x[i]-1]^sum[y[i]]);
return 0;
}