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;

}

　　

相关文章