本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-18 09:35:47

[ABC367F] Rearrange Query

题目考察：哈希，前缀和。
题目简述：
给你两个序列 $\{a_n\}$ 和 $\{b_n\}$，$q$ 次询问，每次询问都给出四个数 $l_1,r_1,l_2,r_2$，问重新排列 $a_{l_1},a_{l_1+1},\dots,a_{r_1}$ 后，排列后的这段序列是否与 $b_{l_2},b_{l_2+1},\dots,b_{r_2}$ 相等。
数据范围：

• $1\le n,q\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i,b_i\le n$
• $1\le l_1,r_1,l_2,r_2\le n$

我们需要一个算法（或数据结构）来快速的判断两个序列是否相等，于是我们想到了哈希。
我们用前缀和求出 $\displaystyle suma_i=(\sum_{j=1}^ia_j^X)\bmod p$（$X$ 是个常数，$p$ 是模数），$sumb$ 同理。
然后我们对于每次查询判断 $suma_{r_1}-suma_{l_1-1}$ 是否等于 $sumb_{r_2}-sumb_{l_2-1}$ 即可。
防止被卡，我们就跑一个四哈希。

时间复杂度为 $\Theta(n\log X+q)$。
代码