CF1746F Kazaee（随机化哈希）

真的做不来这种题怎么办/ll

题意

给定 \(n\) 个数，\(q\) 次操作：

• 单点修改一个数的值。
• 查询区间内所有数的出现次数是否均为 \(k\) 的倍数。

\(n,q\le 3\times10^5\)。

分析

一眼看上去只能带修莫队，而且常数还巨大无比。

这种随机化哈希题一般是考虑一个必要不充分条件，但是充分的概率足够，这样可以考虑多做几次（有的甚至做一次就行），使得答案大概率正确。

考虑给每个数赋一个随机权值，那么如果合法那么区间权值和显然是 \(k\) 的倍数，但反过来是假的，比如说如果一个数的权值赋到了 \(k\) 的倍数，那么无论该数出现几次和永远是 \(k\) 的倍数。单次查询的错误率感性理解一下是 \(\frac{1}{k}\) 的（？）。那么我们做很多次（结合时间复杂度取 \(K=[25,30]\)），正确率就有保证了。

使用 BIT 维护区间和，时间复杂度 \(O(Kn\log n)\)。

代码非常好写，不放了。