【题目链接】 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;
} 

• 相关文章
• 全局相关文章