题解 P6688 【可重集】

sol of D: 下文令n，q同阶 ## subtask1 按照题意模拟，每次把两个区间排序并一一比较即可。时间复杂度$O(n^2\log_2n)$ ## subtask2 题意其实是要你判断区间排序后差分数组是否相同，且有一个显然的结论：$k$只有可能是$\min \{a_{l_2}\dots a_{r_2}\}-\{\min a_{l_1}\dots a_{r_1}\}$，于是我们暴力判断2个区间对应的数字个数是否相同即可。可以用树状数组做到$O(nV\log n)$,使用大家高超的分块技巧可以做到时间复杂度$O(n\sqrt{n}+nV)$ ## subtask3 维护区间k次方和，然后$O(k^2)$地对于任意$1\leq d \leq k$求出$\sum (a_i+b)^d$，依次比较是否相同即可，时间复杂度$O(nk\log n+nk^2)$,k需要开到$\log n$才能保证正确性。 [k较小的hack方法](https://www.luogu.com.cn/discuss/show/105778) ## subtask4 我们本质上是要求每个数在区间中出现的次数相同，如果给每个数一个随机的映射值$\operatorname{Hash_v}$，两个区间的映射值是否相同就可以作为两区间是否本质相同的依据。 现在关键问题变成了如何把$a_l\dots a_r$的哈希值快速转化为$a_l+k\dots a_r+k$的哈希值？ 令$\operatorname{Hash_v}=\operatorname{g^v}$即可快速转换。 tips:很多人被卡常都是因为使用了线段树，用线段树是因为要求带修区间最小值，事实上并不必要，两区间的和之差除以区间长度就是题目中的k，所以可以直接用树状数组维护。