题解 P6688 【可重集】

skydogli · 2020-07-28 19:10:48 · 题解

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方法

subtask4

我们本质上是要求每个数在区间中出现的次数相同，如果给每个数一个随机的映射值\operatorname{Hash_v}，两个区间的映射值是否相同就可以作为两区间是否本质相同的依据。

现在关键问题变成了如何把a_l\dots a_r的哈希值快速转化为a_l+k\dots a_r+k的哈希值？

令\operatorname{Hash_v}=\operatorname{g^v}即可快速转换。

tips:很多人被卡常都是因为使用了线段树，用线段树是因为要求带修区间最小值，事实上并不必要，两区间的和之差除以区间长度就是题目中的k，所以可以直接用树状数组维护。