异或 xor
题目大意:有一个 n 个元素的数列 a，要进行 m 次查询，每次查询形式如下： 1. 给出两个整数 l,r ，表示查询区间的左右端点 2. 取出区间 [l,r] 中的所有出现了偶数次的整数。比如 1,2,1,2,1,则会 取出一个数 2 3. 将取出来的数全部异或起来，并将该异或值作为本次查询的答案 由于 David 计算能力很差，于是他请你来帮他计算一下每次询问的答案
数据结构好题
我们发现如果维护一个区间出现奇数次的数字的异或和就好办了,因为偶数次的都自己暴毙了(k^k=0)
所以我们希望对问题进行转化:每个区间中每个数字去掉出现的第一个之后,剩下的数字的异或和
用线段树或者树状数组来维护
在l的位置插入r以及他的问题id
然后一遍扫过去,统计答案,不断更新
代码如下: 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
59
60
61
62
63
64
65
using namespace std;
typedef pair<int, int> pr;
const int N = 1e6 + 66;
vector<pr>q[N];
map<int, int>vis, pre;
int n, m, now;
int a[N], b[N];
int nex[N], ans[N], tree[N];
inline void updata(int x, int val)
{
while (x <= n)
{
tree[x] ^= val;
x += lowbit(x);
}
return;
}
inline int query(int x)
{
int res(0);
while (x)
{
res ^= tree[x];
x -= lowbit(x);
}
return res;
}
signed main()
{
int i, j, l, r;
n = read();
for (i = 1; i <= n; ++ i)
{
a[i] = read();
++ vis[a[i]];
nex[pre[a[i]]] = i;
pre[a[i]] = i;
if (vis[a[i]] > 1) now ^= a[i];
b[i] = now;
}
m = read();
for (i = 1; i <= m; ++ i)
{
l = read(), r = read();
q[l].push_back(pr(r, i));
}
for (i = 1; i <= n; ++ i)
{
for (j = 0; j < (int)q[i].size(); ++ j) ans[q[i][j].second] = query(q[i][j].first) ^ b[q[i][j].first];
l = nex[i];
if (l) updata(l, a[i]);
}
for (i = 1; i <= m; ++ i) put(ans[i]);
return 0;
}
后记:
考虑到代码的实现,第一次写博客的时候,并未深刻搞懂代码实现,于11.25更新.
说明几个东西的定义:
b数组表示不计算每一个a[i]第一次出现的情况的异或和
tree数组表示的我们不断修改的一些东西.
来自zlc大佬的讲解:
1 | 就是询问离线，按照左端点排序，然后每次移动当前的左端点，修改整体的状态，并同时查询答案； |