Random Hash

模型 $1$：给定一个长度为 $n$ 的序列 $a$，可以有重复元素，问：

• $1.$ 给定一个子区间 $[l , r]$，如何判断 $[l , r]$ 中所有数都出现了偶数次。错误的概率是多少。
• $2.$ 给定一个子区间 $[l , r]$。根据 $1$，已知区间 $[l , r]$ 有的元素出现了奇数次， 如何判断 $[l , r]$ 中 有且仅有 一个数出现了奇数次。错误的概率是多少。

• • $1.$ 给每一个在序列中出现的数 $x$ 随机地赋上一个 $0 \sim 2^{64} - 1$ 内的数 $c_x$。考虑到若区间 $[l , r]$ 的数都出现了偶数次，则区间异或和必然为 $0$。因此，若区间 $[l , r]$ 的 $c_x$ 的异或和为 $0$，我们就认为 $[l , r]$ 的数都出现了偶数次。
  • $1.$ 一个结论：假设有一个集合 $A$，里面的元素在 $0 \sim 2^{64} - 1$ 完全随机，并且 至少存在一个数出现了奇数次，则我们认为 不管集合 $A$ 有多少个元素，$A$ 内部所有元素的异或和 $x$ 等于 $0 \sim 2^{64} - 1$ 内的某一个数 $y$ 的概率均为 $\dfrac{1}{2^{64}}$（即把所有数异或起来的结果等价于给一个变量 $x$ 随机赋一个 $0 \sim 2^{64} - 1$ 的权值）
  • $1.$ 当区间 $[l , r]$ 有的数出现了奇数次，但区间异或和为 $0$ 时，答案会出错。根据刚才的结论，出错的概率为 $\dfrac{1}{2^{64}}$
• • $2.$ 设区间 $[l , r]$ 的 $c_x$ 的异或和为 $\text{sum}$，若 $\text{sum}$ 在 序列 $c$ 中出现，我们就认为区间 $[l , r]$ 只有一个数出现了奇数次。
  • $2.$ 当区间 $[l , r]$ 有多个数出现了奇数次且区间异或和 $\text{sum}$ 在 $c_1 \sim c_n$ 中出现过。错误的概率最坏为 $n\times \dfrac{1}{2^{64}}$。由于 $\text{sum}$ 在原序列中出现的概率就已经很小了，所以我们不需要再去判断 $\text{sum}$ 是否在区间 $c_l \sim c_r$ 中出现过

模型 $2$：给定两个集合 $A$ 和 $B$，问：

• $1.$ 若 $A$ 和 $B$ 均满足内部 无重复元素 出现，如何判定 $A$ 和 $B$ 全等。错误的概率是多少。
• $2.$ 若 $A$ 和 $B$ 内部均可能 存在重复元素，如何判定 $A$ 和 $B$ 全等。错误的概率是多少。

• • $1.$ 给 $A$ 和 $B$ 每一个出现过的数值 $x$ 赋上一个 $0\sim 2^{64} - 1$ 的数值 $c_x$。若 $A$ 所有元素 $c_x$ 的异或和 $s_1$ 等于 $B$ 所有元素异或和 $s_2$，则我们认为 $A$ 和 $B$ 全等。
  • $1.$ 当 $A$ 和 $B$ 不全等（即存在一个数只在 $A$ 或者 $B$ 出现），并且 $s_1 = s_2$ 时，会出错。考虑让 $A$ 和 $B$ 相同元素抵消。这样，对于一个没有被抵消的数 $x$，它要么只在 $A$ 中出现一次，要么只在 $B$ 中出现一次。因此 $s_1$ 和 $s_2$ 两个变量就 独立 并且完全在 $0\sim 2^{64} - 1$ 随机。
• • $2.$ 由于集合内有重复元素，所以异或的方法不管用了（比如 $A = \{2 , 2\}$，$B = \{4 , 4\}$）。考虑令 $s_1$ 为 $A$ 所有元素的 $c_x$ 的和，$s_2$ 为 $B$ 所有元素 $c_x$ 的和。若有 $s_1 = s_2$，我们认为 $A$ 和 $B$ 全等。
  • $2.$ 如何计算错误的概率？考虑消去 $A$ 和 $B$ 公共元素，则 $A$ 和 $B$ 独立，并且在 $0\sim 2^{64} - 1$ 内完全随机。则错误的概率为 $\dfrac{1}{2^{64}}$

模型 $3$：给定一个序列 $a$，问：

• $1.$ 给定一个整数 $k$。然后再给 $q$ 组询问，每次询问给定两个参数 $l$ 和 $r$，表示询问区间 $[l , r]$ 内是否所有数出现次数都是 $k$ 的倍数。
• $2.$ 给 $q$ 组询问，每次询问给定三个参数 $l$，$r$，$k$ 表示询问区间 $[l , r]$ 是否所有数出现次数都是 $k$ 的倍数。

• $1.$ 给每一个出现的数 $x$ 随机赋一个 $0 \sim 2^{64} - 1$ 内的权值 $c_x$，使得 $k$ 个相邻的并且相等的 $c_x$ 异或和为 $0$（注意，它们三个在原序列中不一定相邻），这样，若所有数出现次数都是 $k$ 的倍数，则区间异或和必然为 $0$，错误的概率为 $\dfrac{1}{2^{64}}$
• $2.$ 给每一个出现过的数 $x$ 随机赋一个权值 $c_x$，求出这个区间 $c$ 值的和 $\text{sum}$，若 $\text{sum}$ 不是 $k$ 的倍数，输出 NO。错误的概率最坏为 $\dfrac{1}{2}$，随机 $30$ 次，错误的概率最坏为 $\dfrac{1}{2^{30}}$

P4065 [JXOI2017] 颜色

• 给定一个长度为 $n$ 的整数序列，每一个数都有一个颜色 $a_i$
• 定义“删除颜色 $x$” 为把所有的满足 $a_i = x$ 的 $a_i$ 删掉。问有多少种删除颜色的方案，使得最后剩下的数形成原序列的一个子区间。
• 例如，假设 $a$ 初始为 $\{1 ,2 ,3 ,2 ,2\}$，若删掉颜色 $3$，则变为 $\{1,2\}$ 和 $\{2, 2\}$，不是一个子区间；若删掉颜色 $1$，则变为 $\{2,3,3,2\}$，是一个子区间。
• 两个方案不同当且仅当至少存在一个颜色 $i$ 只在其中一个方案中被删去。
• $1\leq n \leq 3\times 10^5$，$1\leq a_i \leq n$

• 设 $[l , r]$ 为删除后的子区间，则任意一个在区间 $[l , r]$ 的颜色 $x$，都应该满足：序列中 所有的 颜色 $x$ 只在 区间 $[l , r]$ 出现。
• 考虑给每一个位置 $i$ 赋一个 $0\sim 2^{64} - 1$ 范围内的数 $c_i$，并且要满足，对于任意一个颜色 $x$，所有满足 $a_i = x$ 的 $c_i$ 的异或和为 $0$。
• 而当一个区间 $[l , r]$ 区间异或和为 $0$，并不能保证区间 $[l , r]$ 是合法的。当一个区间 $[l , r]$ 区间异或和不为 $0$ 时，却 一定 能保证区间 $[l , r]$ 是非法的。
• 因此，我们考虑当区间 $[l , r]$ 异或和为 $0$ 时（即当区间 $[l , r]$ 不合法但区间异或和为 $0$ 时），出错的概率。
• 区间不合法意味着存在一个颜色 $x$，使得颜色 $x$ 不只是在区间 $[l , r]$ 出现。此时我们认为区间 $[l , r]$ 异或和在 $0\sim 2^{64} - 1$ 中等概率出现，因此判定一个区间是否和合法区间时，出错率为 $\dfrac{1}{2^{64}}$，正确率为 $1 - \dfrac{1}{2^{64}}$。
• 设 $S_i$ 表示 $c_1 \sim c_i$ 的异或和。则剩下的任务是统计有多少个区间 $[l , r]$ 使得区间 $S_r \oplus S_{l - 1} = 0$ 即 $S_r = S_{l - 1}$
• 代码

S2oj #1497 树

• 给定一棵 $n$ 个结点的树，树上每条边有边权
• 给你 $q$ 组询问，每次给定 $u$ 和 $v$，问 $u \rightarrow v$ 这条路径上的边权是否能重新排列，形成一个回文序列。强制在线。
• $1\leq n \leq 10^6$，$1\leq q \leq 2\times 10^7$

• 若一个序列可以形成回文序列，需要满足以下两个条件 之一：
• • $1.$ 若序列长度为奇数，则有且仅有一个数出现奇数次。
  • $2.$ 若序列长度为偶数，则不存在一个数出现奇数次。
• 给每一种边权 $x$ 随机赋上一个在 $0\sim 2^{64} - 1$ 的值 $c_x$。
• 设 $d_u$ 表示 $1 \sim u$ 路径上所有 $c_x$ 的异或和。
• 则查询时判定 $d_u \oplus d_v$ 是否等于 $0$ 或者等于某一个在 树的边权 出现过的 $c_x$ 即可。
• 考虑单次查询错误的概率，即当路径上不满足条件 $1$ 和条件 $2$ 时，异或和等于 $0$ 或者某一个 $c_x$ 的概率，最坏为 $(n + 1) \times \dfrac{1}{2^{64}}$，是一个非常小的数值。
• 代码

CF869E The Untended Antiquity

• 给定一个 $n \times m$ 的网格。
• $q$ 次操作，每次给定三个参数 $\text{opt}$，$x_1$，$y_1$，$x_2$，$y_2$
• • 若 $\text{opt} = 1$，表示给以 $(x_1,y_1)$ 为左上角，$(x_2 , y_2)$ 为右下角的矩形围上篱笆。
  • 若 $\text{opt} = 2$，表示给把以 $(x_1,y_1)$ 为左上角，$(x_2 , y_2)$ 为右下角的矩形的篱笆拆掉（保证这个篱笆存在）
  • 若 $\text{opt} = 3$，表示查询方格 $(x_1 , y_1)$ 和方格 $(x_2 , y_2)$ 是否连通
• 数据保证任意修建的两个篱笆都不相等，并且对于任意两个篱笆，要么包含，要么完全不相交。
• $1 \leq n, m \leq 2500$，$1 \leq q \leq 10^5$

• 考虑如何判定两个方格连通。给每一个篱笆一个编号，设围住 $(x_1 , y_1)$ 的篱笆集合为 $S_{x_1 , y_1}$，围住 $(x_2 , y_2)$ 的篱笆集合为 $S_{x_2 , y_2}$。发现若满足 $S_{x_1 , y_1} = S_{x_2 , y_2}$，则 $(x_1 , y_1)$ 和 $(x_2 , y_2)$ 连通。
• 如何判定两个集合全等？考虑给每一个编号（编号记做 $i$）的篱笆赋一个 $0\sim 2^{64} - 1$ 的权值 $c_i$。则只需要判断 $S_{x_1 , y_1}$ 内所有 $c_i$ 的异或和 $v_1$ 是否等于 $S_{x_2 , y_2}$ 内所有 $c_i$ 的异或和 $v_2$。
• 如何给一个矩形范围内所有的方格的集合 $S_{x , y}$ 都添加上编号 $i$？使用二维差分 $+$ 二维树状数组即可。
• 代码

ABC 250E Prefix Equality

• 给定两个长度为 $n$ 的数列 $a$ 和 $b$。
• 有 $q$ 组询问，每次询问给定两个参数 $i$ 和 $j$，询问 $a_1 \sim a_i$ 排序去重后形成的序列 $A$，是否等于 $b_1 \sim b_j$ 排序去重后形成的序列 $B$。
• $1\leq n \leq 2\times 10^5$，$1 \leq q \leq 2\times 10^5$

• 考虑模型 $2$，给每一个在 $a$ 或者 $b$ 出现过的数随机赋一个 $0\sim 2^{64} - 1$ 的权值。
• 维护 $a$ 的异或前缀和 $s_1[i]$ 和 $b$ 的异或前缀和 $s_2[i]$
• 对于 $a[i]$，如果存在一个 $j < i$ 使得 $a_j = a[i]$，则只需令 $s_1[i] \leftarrow s_1[i - 1]$ 即可。否则令 $s_1[i] \leftarrow s_1[i - 1] \oplus c[a[i]]$
• 最后判定 $s_1[i]$ 和 $s_2[j]$ 是否相等即可。
• 代码

CF1418G Three Occurrences

给定一个长度为 $n$ 的序列 $a$

问有多少个子区间满足：所有数都 恰好 出现了 $3$ 次。

$1 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq n$

• 对于一个区间 $[l , r]$，若区间 $[l , r]$ 所有数出现次数恰好为 $3$ 当且仅当：
• • $1.$ 所有数出现次数都 $\leq 3$
  • $2.$ 所有数出现次数都是 $3$ 的倍数。
• 枚举右端点 $r$，考虑统计 $1 \sim r$ 有多少个 $l$ 使得区间 $[l , r]$ 满足条件。
• 对于 $1$，枚举 $r$ 的同时维护最小的 $j$，使得当 $l$ 满足 $j \leq l \leq r$ 时，有 $[l , r]$ 所有数出现次数不超过 $3$。
• 给每一个数 $x$ 随机赋一个 $0\sim 2^{64} - 1$ 内的权值 $c_x$，使得三个相邻的值相同的 $c[a[i]]$，$c[a[j]]$，$c[a[k]]$ 异或和为 $0$
• 然后求出 $c[a[i]]$ 的前缀异或和 $S[i]$，即 $c[a[1]] \sim c[a[i]]$ 的异或和。
• 对于一个区间 $[l , r]$，若满足 $S[r] \oplus S[l - 1] = 0$，即 $S[r] = S[l - 1]$，则我们认为区间 $[l , r]$ 所有数的出现次数是 $3$ 的倍数。错误概率为 $\dfrac{1}{2^{64}}$。
• 那么剩下的任务就是对于一个 $r$，统计 $j \sim r$ 内有多少 $l$ 使得 $S[r] = S[l - 1]$，用 std::map 作为桶即可。
• 代码

P8819 [CSP-S 2022] 星战

• 给定一张 $n$ 个点 $m$ 条边的有向图
• 给定 $q$ 个操作，首先给定一个参数 $t$ 表示操作类型：
• • 若 $t = 1$，表示摧毁一条边 $u\rightarrow v$，数据保证这条边存在。
  • 若 $t = 2$，表示摧毁所有指向 $u$ 的边 $v \rightarrow u$
  • 若 $t = 3$，表示恢复一条边 $u \rightarrow v$，数据保证 $u \rightarrow v$ 这条边已经被摧毁。
  • 若 $t = 4$，表示恢复 最初 所有指向 $u$ 的边 $v \rightarrow u$
• 每次操作后，请判断当前的图是否是一个内向基环树森林。如果是输出 YES，否则输出 NO。
• $1\leq n \leq 5\times 10^5$，$1 \leq q \leq 5\times 10^5$

• 内向基环树森林 $\leftrightarrow$ 所有的点有且仅有一条出边。
• 最直接的想法是给每一个点 $i$ 维护一个 $\text{cnt}[i]$ 表示 $i$ 的出度，每次操作完之后看看所有点的出度是否都是 $1$。但是对于 $t = 2$ 和 $t = 4$ 就有些棘手了，因为对于所有的 $v\rightarrow u$，我们需要给所有的 $v$ 执行 $\text{cnt}[v] \leftarrow \text{cnt}[v] - 1$ 或者 $\text{cnt}[v] \leftarrow \text{cnt}[v] + 1$
• 发现似乎维护每一个点的入度更方便一些。但入度并不能帮助我们判定一个图到底是否是内向基环树森林。
• 考虑把每一条边 $u \rightarrow v$ 的出点 $u$ 放到一个多重集合 $S$， 然后把 $1 \sim n$ 每一个点放到一个多重集合 $T$ 里。发现如果我们想判定这个图是否是內向基环树森林，我们只需要判定 $S$ 和 $T$ 是否全等。
• 立刻想到模型 $2$，给每一个点 $x$ 随机赋一个 $0\sim 2^{64} - 1$ 范围内的数 $c_x$。设 $\text{sum}$ 表示集合 $S$ 的 $c_x$ 的和。若要判定 $S$ 和 $T$ 是否全等，我们只需要判定是否 $\text{sum} = \displaystyle \sum_{i = 1}^{n} c_i$
• 设 $s_u$ 表示所有指向 $u$ 的点 $x$ 的 $c_x$ 之和。设 $d_u$ 表示 最初 指向 $u$ 的点的 $x$ 的 $c_x$ 之和。
• • 若 $t = 1$，令 $\text{sum} \leftarrow \text{sum} - c_u$，$s_v \leftarrow s_v - c_u$
  • 若 $t = 2$，令 $\text{sum} \leftarrow \text{sum} - s_u$，$s_u = 0$
  • 若 $t = 3$，令 $\text{sum} \leftarrow \text{sum} + c_u$，$s_u \leftarrow s_v + c_u$
  • 若 $t = 4$，令 $\text{sum} \leftarrow \text{sum} + d_u - s_u$
• 代码

CF1746F Kazaee

给定一个整数序列 $a$，有 $q$ 次操作，每次操作有两种类型：

• 把某一个位置 $i$ 的值修改成 $x$，即 $a_i \leftarrow x$
• 给定 $l$，$r$，$k$ 三个参数，每次询问是否区间 $[l , r]$ 的数出现次数都是 $k$ 的倍数。
• $1 \leq n \leq 3 \times 10^5$，$1 \leq q \leq 3\times 10^5$

• 给每一个出现过的值 $x$ 随机赋一个在 $0 \sim 2^{31} - 1$ 的值 $c_x$。如果所有数在区间 $[l , r]$ 出现次数都为 $k$ 的倍数，则区间 $[l , r]$ 内所有数的和一定为 $k$ 的倍数！
• 当区间 $[l , r]$ 存在一些数出现次数不是 $k$ 的倍数，而区间和是 $k$ 的倍数时，答案会出错。感性证明：肯定是 $k$ 越小，冲突的概率越大，则 $k$ 最小可以取 $2$（因为 $k = 1$ 肯定输出 YES）；肯定是当区间内只有一种数的时候随机性更强一些。
• 则设这个数为 $x$，以及其出现的次数 $\text{cnt}$，则需要计算 $\text{cnt} \times c_x \bmod k = 0$ 的概率。令 $\text{cnt} \leftarrow \text{cnt} \bmod k$，再令 $\text{cnt} \leftarrow \dfrac{\text{cnt}}{\gcd(\text{cnt} , k)}$，$k \leftarrow \dfrac{k}{\gcd(\text{cnt} , k)}$，最终使得 $k$ 和 $\text{cnt}$ 互质。则需要满足 $c_x \bmod \dfrac{k}{\gcd(\text{cnt} , k)} = 0$，而由于 $\text{cnt} < k$，则 $\dfrac{k}{\gcd(\text{cnt} , k)} \geq 2$。由于 $c_x$ 纯随机，所以错误的概率最坏是 $\dfrac{1}{2}$
• 重复上述操作 $30$ 次：给所有值随机赋值，用树状数组或者线段树维护区间 $c$ 值的和，只要这 $30$ 次内有 $1$ 次发现区间和不是 $k$ 的倍数，就可以直接判定本次询问为 NO。
• 错误的概率为区间不满足每一个数出现次数都是 $k$ 的倍数，但是这 $30$ 次每次区间和都是 $k$ 的倍数，概率最坏为 $(\dfrac{1}{2})^{30} = \dfrac{1}{2^{30}}$，可以接受。
• 注意每次随机时，不应该直接把 $c$ 数组设置成 unsigned int 或者 unsigned long long。因为树状数组单点修改时，有可能会加上一个负数，而这两个数据类型是不能表示负数，会自动对 $2^{32}$ 或者 $2^{64}$ 取模，而取模之后 $\bmod$ $k$ 就失去了意义。
• 代码

[ABC367F] Rearrange Query

• 给定一个长度为 $n$ 的正整数序列 $a$ 和 $b$
• 有 $q$ 组询问，每次询问给定两个参数 $l$ 和 $r$，问 $a_l \sim a_r$ 重新排列后是否能等于 $b_l \sim b_r$。
• $1 \leq n \leq 2\times 10^5$，$1\leq q \leq 2\times 10^5$，$1\leq a_i,b_i \leq n$

• 把 $a_l \sim a_r$ 看做集合 $A$，把 $b_l \sim b_r$ 看做集合 $B$，则只需判定集合 $A$ 和 集合 $B$ 是否相等即可。
• 由于 $A$ 和 $B$ 内部可能有重复元素出现，所以用 和哈希 Sum-Hash 而不是异或哈希 Xor-Hash
• 给每一个在序列 $A$ 或者 $B$ 出现的数 $x$ 随机赋一个 $0 \sim 2^{64} - 1$ 的数值 $c_x$
• 则维护 $a$ 序列 $c_{a_1} \sim c_{a_i}$ 的和 $s_1[i]$，以及 $b$ 序列 $c_{b_1} \sim c_{b_i}$ 的和 $s_2[i]$。查询时，判断 $s_1[r] - s_1[l - 1]$ 和 $s_2[r] - s_2[l - 1]$ 是否相等即可。