题解: 我们维护前缀异或和 求出区间[l,r]范围内出现奇数次个数的异或和 然后用树状数组维护区间[l,r]范围内 出现过的数字的异或和 然后两者异或起来就是答案
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
typedef struct node{
int id,l,r;
friend bool operator<(node aa,node bb){return aa.r<bb.r;}
}node;
node que[MAXN];
ll ans[MAXN],a[MAXN];
vector<ll>vec;
int pre[MAXN],n;
ll sum[MAXN],p[MAXN];
int get_id(int x){return x&(-x);}
void update(int x,ll vul){
for(int i=x;i<=n;i+=get_id(i))sum[i]^=vul;
}
ll Sum(int x){
if(x<=0)return 0;
ll ans1=0;
for(int i=x;i>0;i-=get_id(i))ans1^=sum[i];
return ans1;
}
int main(){
n=read();
inc(i,1,n)a[i]=read(),vec.pb(a[i]);
sort(vec.begin(),vec.end());
int sz=unique(vec.begin(),vec.end())-vec.begin();
int q=read();
inc(i,1,q)que[i].l=read(),que[i].r=read(),que[i].id=i;
sort(que+1,que+q+1);
int tot=1;
inc(i,1,q){
while(tot<=n&&tot<=que[i].r){
int t=lower_bound(vec.begin(),vec.begin()+sz,a[tot])-vec.begin()+1;
if(pre[t])update(pre[t],a[tot]);
update(tot,a[tot]);
pre[t]=tot;p[tot]=p[tot-1]^a[tot];
tot++;
}
ll t1=p[que[i].r]^p[que[i].l-1];
ll t2=Sum(que[i].r)^Sum(que[i].l-1);
ans[que[i].id]=t1^t2;
}
inc(i,1,q)printf("%lld
",ans[i]);
}
5476: 位运算
Time Limit: 5 Sec Memory Limit: 512 MBSubmit: 42 Solved: 16
[Submit][Status][Discuss]
Description
有一个长为n的自然数序列Ai。
有m次询问，每次询问区间[l,r]中出现次数为偶数的数的异或和。
Input
第一行一个整数n。
第二行一共n个整数表示序列Ai。
第三行一个整数q。
接下来共q行，每行2个整数l,r，表示询问的区间。
N,M<=3*10^5
Ai<2^32
Output
共q行，每行一个整数ans表示答案。
（如果不存在出现偶数次的数，那么答案就是0）
Sample Input
5
1 1 5 5 1
4
2 5
5 5
1 4
1 5
1 1 5 5 1
4
2 5
5 5
1 4
1 5
Sample Output
4
0
4
5
0
4
5