对集合的一些判断可以考虑随机化哈希。
给每个数随一个权，如果集合 \(S\) 中每个数的出现次数都是 \(k\) 的倍数，那 \(S\) 中元素的权值之和就会是 \(k\) 的倍数，否则会是一个在 \([0,k)\) 中随机的值。
也就是说如果这个集合不满足要求，我们做一次这个检测，有 \(\frac{k-1}{k}\) 的概率检测出这个集合存在数出现次数不为 \(k\) 的倍数。并且对于满足要求的集合这个检测一定能通过。
那我们一次检测不出的概率是 \(\frac{1}{k}\)，而这个东西显然是可以通过设不同的随机权值重复检测的，\(t\) 次检测都检测不出的概率就是 \((\frac{1}{k})^t=\frac{1}{k^t}\)，这个东西的缩小速度是指数级别的。
但是注意到还需要每个询问都正确，所以正确率是 \((1-\frac{1}{k^t})^{n}\)，但是错误率缩小速度仍然很快，取 \(t=30\) 就可以保证正确率达到 \(99.97\%\)。
单点修改，区间权值和可以通过树状树组简单维护，那时间复杂度即为 \(\Theta(t\cdot n\log n)\)，\(t=30\)。