一、哈希介绍
哈希是一个函数，把一个复杂的数据压缩成一个更简单，容易存储的东西。
我们判断两个复杂的数据是否相等，只需要判断它们俩的哈希函数是否相等。
简单来说，哈希损耗了原数据的减少了正确率，有利于复杂数据的辨识。
常见的哈希有：字符串哈希，集合哈希，树哈希
我们先来说说字符串哈希。
1. 字符串哈希：辨识两个字符串是否相等
目前字符串哈希总共有三种，分别是：单模，双模，自然溢出。
单模：类似进制，\(f(s) = \sum _\limits {i = 0} ^{s.size() - 1} s_i \times b^i \mod p\)，其中可以自己取的变量是：所有字符（\(s_i\)）的权值，\(b\)，\(p\)。一般来说，\(s_i\) 的选取可以自己随便造，只需要保证不同的 \(s_i\) 权值不同。\(b\) 是底数，需要比 \(s_i\) 的种数多（进制原理），\(p\) 是一个大质数。
双模：就是两个单模哈希，只有在两个哈希函数都相同的情况下才能认为这两个字符串相等。注意底数和模数要互不相等。实际上，你还可以搞出三模，四模，……
自然溢出：给懒人设计的算法，本质上就是把 \(p\) 设成了 \(2^{32}\) 或 \(2^{64}\)，不需要手动取模。
现在我们来讨论一下这三个算法怎么卡，以及它们的时间优劣。
单模：非常好卡，随机的字符串就能卡掉。为什么呢？你可以去了解一下生日悖论。一个长度为 \(10^5\) 的字符串有大约 \(10^{10}\) 个子串，这会让哈希函数的错误率指数上升，导致错误。
双模：你想卡我？真的假的？根据 CRT 的结论，你可以求出哈希函数模 \(p1 * p2\) 的值，也就是说，如果模数大到 \(10^{18}\) 以上，那么就有 \(10^{36}\) 种不同的哈希函数值。除非你 RP = -114514，否则你写了这个是不可能卡掉的。
自然溢出：由于模数确定，很容易被出题人刻意构造卡掉。许廷强在集训队论文里面给出了一种卡掉自然溢出的方式。自此，所有出题人都学会了卡自然溢出。
总结：如果这题不是卡常，直接用双模就完事了。
2. 集合哈希：辨识两个集合（可重集）是否相等
这就是我听不懂的和哈希是吧
实际上，这种哈希函数有很多。
你可以随意构造，例如，你可以把函数设置为 \(f(A) = \sum _\limits {x \in A} x \mod p\)。
当然，这太容易被卡掉了，所以你还可以创造：\(f(A) = \sum _\limits {x \in A} x^3 \mod p\)
如果这也能被卡掉，你还可以：\(f(A) = \sum _\limits {x \in A} (x + x^3) \times \sin(x) \mod p\)
所以集合哈希是非常好构造的，你可以发挥你的创造力。冷知识：\(\sin\) 是一个非常安全的函数，很难会被卡。
3. 树哈希
本人没 AC 模板，所以没写。咕咕咕~
二、做题记录
P6688 可重集
题意：给定一个长度为 \(n\) 的序列 \(a\)，你需要实现以下两个操作共 \(q\) 次：
1.将 \(a_x\) 改成 \(y\)
2.判断两个区间是否本质相同，保证这这两个区间长度相等。
本质不同定义：将两个长度为 \(n\) 的序列 \(a\)，\(b\) 排序后得到序列 \(p\)，\(q\)。如果存在一个整数 \(k\) 使得 \(i \in [1, n] \cap Z, p_i + k = q_i\)，那么 \(a\)，\(b\) 本质相同，否则本质不同。
数据范围：\(1 \leq n, q \leq 10^6，0 \leq a_i, y \leq 10^6\)。
这里提供一种题解中没有的，神奇的做法。
发现两个区间本质相同，当且仅当它们的方差相同。
所以我们直接线段树维护区间的方差即可。注意到方差的最大值不可能超过 \(10^{18}\)，直接算就行了，连哈希都不用。当然，方差是将所有的数减去平均数的平方和，你可以考虑变成立方和或者114514次方和来增加安全性，毕竟我写方差被卡了。
哈希：我免费了