Codeforces 703D (区间内出现偶数次的数的异或和)_区间内出现偶数次的数异或和

题意：给定你一个长度为n的序列，然后m个询问，每次询问给出L和R，问你在这个区间内出现次数为偶数次的数(每个数只取一个)，他们的异或和为多少。

思路：出现次数为偶数次这些异或都会变成0，所以我们直接求区间异或和，求出来的出现次数为奇数词的数的异或和，假如我们能求得这个区间内不同的数的异或和，那他们二者异或一下就可以得到我们想要的答案了。
然后问题就变成了怎么求区间内不同数的异或和呢。m个询问，我们可以离线处理，按照右端点从小到大的顺序排序，然后每次只去更新距离当前右端点r最近的值的位置，再把这个位置之间的位置的值置为0，这样每次区间内我们算的就是一个唯一存在的值，又因为离线处理，按照右端点扫一遍，复杂度是可以的。
这样我们就用一个树状数组维护这个特殊的区间异或和即可。

代码：

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e6 + 7;
//对于这种m个询问的题目 可以多想一下 能不能离线搞 这个题就是离线之后 按右端点找就可
int pre[MAXN];//当前数的上一次出现的位置
map<int,int>mp;//记录一下每个数出现的位置
int sxor[MAXN],n,m,ans[MAXN],a[MAXN],c[MAXN];

struct Q{//存询问
	int l,r,id;
}q[MAXN];
bool cmp(Q a,Q b){ return a.r < b.r; }
bool ccmp(Q a,Q b){ return a.id < b.id; }

int lowbit(int x){ return x & (-x); }
void update(int p,int v){ while(p <= n){ c[p] ^= v;p += lowbit(p);  } }
int query(int p){
	int ans = 0;
	while(p){ ans ^= c[p];p -= lowbit(p); }
	return ans;
}

int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++){
		scanf("%d",&a[i]);
		pre[i] = mp[a[i]];//存一下当前位置的值上一次出现的位置是哪里
		mp[a[i]] = i;
	}
	// for(int i = 1;i <= n;i ++) cout<<pre[i]<<' '; cout<<'\n';
	for(int i = 1;i <= n;i ++) sxor[i] = sxor[i-1] ^ a[i];
	scanf("%d",&m);
	for(int i = 1;i <= m;i ++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q + 1,q + 1 + m,cmp);//按右端点的大小排序 这样保证扫一遍即为答案
	int L,R = 1;
	for(int i = 1;i <= m;i ++){
		while(R <= q[i].r){
			if(pre[R]){//前面出现过的话 我就把它置为0 也就是再异或一下
				update(pre[R],a[R]);
			}
			update(R,a[R]);
			R++;
		}
		L = q[i].l;
		int t = sxor[R-1] ^ sxor[L-1];
		// cout<<R-1<<' '<<L<<endl;
		// cout<<query(R-1)<<"***"<<query(L-1)<<endl;
		ans[q[i].id] = t ^ query(R-1) ^ query(L-1);

	}
	sort(q + 1,q + 1 + m,ccmp);
	for(int i = 1;i <= m;i ++) printf("%d\n",ans[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58