自动搬运

查看原文

来自洛谷，原作者为

	ty_mxzhn 打破天生的劣等感 || 写作悔恨的未来

搬运于2025-08-24 23:01:13，当前版本为作者最后更新于2024-07-23 12:26:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

免责声明：场外选手纯凑热闹。我只是一个 CSP-S 2= 的准退役选手别骂我呜呜呜

注：本题解中哈希是广义的，把一些信息压缩或转化成另一些信息的方式。

看到排列对应，想起自己之前做过的一道题。在看到判定相等，就发现本题可能可以使用哈希解决。2022 年也考了。

作为一道哈希题，第一步肯定需要思考一种可能的哈希方案。容易想到记 $S_{x}$ 为颜色 $x$ 在集合出现时集合的编号所构成的集合。例如：$a_1=\{1,2,3\},a_2=\{2,1,4\},a_3=\{1,3,4\}$ 中，$S_1=\{1,2,3\},S_2=\{1,2\}$。再记多重集合 $H$ 为所有颜色的 $S_x$ 构成的集合。通过手玩发现 $a \cong b \Leftrightarrow H_a =H_b$。

众所周知的，判定两个集合相等可以使用哈希。容易想到，$\displaystyle \prod_{i=1}^m G(\sum_{j=1}^n [i \in S_j] \times p^j) \bmod p_0$ 是一种非常优秀的哈希方式。其中 $G$ 是一个你自己任选的哈希函数。

其实做到这一步已经有可能可以实现了。但是注意到题目中并不需要你对任意的两个数组哈希，而是 $a[l,r]$ 和 $b[l,r]$。这意味着判定具有单调性。我们可以移动 $r$ 然后找最小的 $l$ 满足 $[l,r]$ 被判定为 $\texttt{Yes}$。（双指针）

双指针时哈希值可以支持删除和插入。于是这道题就做完了。

总结：哈希和双指针两个关键点挺难想的。个人感觉板回了去年 NOI 2023 Day1 T1 方格染色较水的局面。

但是作者太菜了，而且怕给其他人带来不便，所以不放代码了。