[ABC367F] Rearrange Query 讲解

zrl123456 · 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)。
代码