推一手蒟蒻 $\color{limegreen}{\texttt {博客}}$ ～

抓住CF爆炸的间隙乘机AC的水题。（滑稽

做这道题只需要知道两个点：

异或前缀性 和 普通莫队算法 。

不妨分开讲。

$\large\color{salmon}{\texttt {异或前缀性：}}$

前缀和可以 $O(1)$ 求解区间和。

前缀积可以 $O(1)$ 求解区间积。

那前缀异或能否 $O(1)$ 求解区间异或呢？

答案是可以的。

$\color{violet}{\texttt {尝试证明：}}$

我们设 $num$ 为一段序列， $xornum_{\small\ l,r}$ 表示这段序列里第 $l$ 到第 $r$ 个元素异或的结果。

手模可知，异或操作满足 结合律 。

把 $xornum_{\small\ 1,l}$ 看成 $a$ ， $xornum_{\small\ l,r}$ 看成 $b$ 和 $c$ 异或的结果，那我们也就有了：

我们又知道异或有以下两个性质：

那么我们可以经历一番移位得出：

佐佑同时异或上一个 $xornum_{\small\ 1,l}$ ，再套用一个结合律得：

用上面两个性质一通转换：

这样，我们就可以 预处理 异或前缀，来 $O(1)$ 求出区间异或的结果～

$\large\color{salmon}{\texttt {普通莫队算法：}}$

定一道莫队题需要看三眼。

  • 第一眼，奇怪的区间查询。

  • 第二眼，可以离线。

  • 第三眼，$N\sqrt{N}$ 能过。

完全符合条件，那就先把莫队的板子敲好。

（这里默认读者一定是会打莫队的QwQ。）

思维难度在 $ins/add$ 和 $del$ 两个函数上。（即 区间扩张/收缩 时的 添/删元素 ）

$\color{violet}{\texttt {如何定制这两个函数？}}$

这里要查的是异或值 $=k$ 的元素对数。

两个数 $a,b$ 做异或，知道其中的一个数 $a$ ，知道异或的结果 $c$ ，则运算的另一个数也是 确定的 ，即 $a\oplus b=c\Leftrightarrow b=a\oplus c$ 。（这也可以用于理解异或的前缀性）

我们增添一个元素 $p$ 进入区间时，它带有一个异或前缀 $xornum_{\small\ 1,p}$ ，查一下区间里 和 $xornum_{\small\ 1,p}$ 异或结果 为 $k$ 的异或前缀的出现次数。

也就是说，我们需要开一个 $cnt$ 数组，维护每个 异或前缀值 当前出现的次数。

参考之前得到的式子，可以推出和 $xornum_{\small\ 1,p}$ 异或得 $k$ 的数，即为 $xornum_{\small\ 1,p}\oplus k$ 。

那么添加一个元素 $p$ 时就应在答案上加上 $cnt[xornum_{\small\ 1,p}\oplus k]$ 。

同理，删除一个元素 $p$ 就应减去 $cnt[xornum_{\small\ 1,p}\oplus k]$ 。

$\color{violet}{\texttt {为什么能保证不重不漏？}}$

因为 $a\oplus b$ 等于 $b\oplus a$ ，可以保证区间中任取两个数，他们之间只计算了一次。

$\color{salmon}{\texttt {实现注意：}}$

  • $cnt$ 数组的大小应为 异或前缀的值域 大小，而非序列中元素个数，这里应为 $2\times 10^6$ 。

  • 正如我们做闭区间和时的 $sum[r]-sum[l-1]$ 一样，这里的闭区间异或也应为 $xornum[r]\oplus xornum[l-1]$ ，一种省力的方法是在输入的时候就把 所有的 $l$ 都减去 $1$ 。

$\color{salmon}{\texttt {Code:}}$

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 7;
#define int long long
int cnt[MAX << 1], num[MAX]; //注意cnt应开2e6
int block[MAX];
int N, M, K;
int sum;
struct query
{
	int L, R;
	int id;
} q[MAX];
bool cmp(query a, query b)
{
	if (block[a.L] != block[b.L])
	{
		return a.L < b.L;
	}
	return (block[a.L] & 1 ? a.R < b.R : a.R > b.R);
}
int xornum[MAX << 1], ans[MAX << 1];
void ins(int p)
{
	sum += cnt[xornum[p] ^ K]; //查对应的异或值
	cnt[xornum[p]]++;		  ///更新出现次数
}
void del(int p) //同上
{
	cnt[xornum[p]]--;
	sum -= cnt[xornum[p] ^ K];
}
signed main()
{
	cin >> N >> M >> K;
	int lenb = sqrt(N);
	for (int i = 1; i <= N; i++)
	{
		cin >> num[i];
		block[i] = (i - 1) / lenb + 1;
		xornum[i] = xornum[i - 1] ^ num[i]; //预处理异或前缀
	}
	for (int i = 1; i <= M; i++)
	{
		cin >> q[i].L >> q[i].R;
		q[i].L--; //像做前缀和一样-1
		q[i].id = i;
	}
	sort(q + 1, q + 1 + M, cmp);
	int L = 1, R = 0;
	for (int i = 1; i <= M; i++) //普通莫队
	{
		while (q[i].L < L)
		{
			L--;
			ins(L);
		}
		while (q[i].R > R)
		{
			R++;
			ins(R);
		}
		while (q[i].L > L)
		{
			del(L);
			L++;
		}
		while (q[i].R < R)
		{
			del(R);
			R--;
		}
		ans[q[i].id] = sum;
	}
	for (int i = 1; i <= M; i++)
	{
		cout << ans[i] << endl;
	}
}

最后更新： 2021年04月19日 11:48

原始链接： https://quest233.github.io/2021/04/17/%E6%B5%85%E8%B0%88%E4%B8%80%E7%B1%BB%E7%AE%80%E5%8D%95%E6%99%AE%E9%80%9A%E8%8E%AB%E9%98%9F%E2%80%94%E2%80%94-CF617E-XOR-and-Favorite-Number-%E9%A2%98%E8%A7%A3/