自动搬运

查看原文

来自洛谷，原作者为

	skydogli 一个人的命运啊，当然要靠自我奋斗，但也要考虑历史的进程

搬运于2025-08-24 22:23:06，当前版本为作者最后更新于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，所以可以直接用树状数组维护。