数列询问 - 题解

数列询问

恕我直言，这题比T5难一些

首先很容易注意到可以用前缀和，所以问题转化为：每次给定 \(S_r - S_{l-1} \equiv k \pmod{p}\) ，求什么时候发生冲突

不难想到把一些关系合并成同一个根节点的更容易判断，例如当：
\(S_6 \equiv S_4 + 1\pmod{p}\)
\(S_4 \equiv S_2 + 2\pmod{p}\)
\(S_2 \equiv S_0 + 1\pmod{p}\)
则有：
\(S_6 \equiv S_0 + 6 \pmod{p}\)

把每个变量看作一个节点，则每个节点都可以用它的根节点+对应的偏移量得到。这样如果有冲突的，那么一定是根节点相同，且偏移量不同，如：
\(S_6 \equiv S_0 + 6 \pmod{p}\) 且 \(S_6 \equiv S_0 + 5 \pmod{p}\)

但是合并2个节点时偏移量会变动（因为根节点变了），如果直接线性递推更新偏移量的话肯定会被善良的出题人卡到爆，所以考虑用并查集，即直接路径压缩把当前节点和根节点合并而不是递推

接下来考虑如何把当前节点和根节点合并时更新偏移量

处理一个新询问

假设新询问给出 \(S_r \equiv S_{l-1} + k\)。

1. 找到 \(r\) 所在集合的根 \(root_r\)，以及 \(l-1\) 所在集合的根 \(root_{l-1}\)。
   在查找根的过程中，同时计算出 \(r\) 到 \(root_r\) 的距离 \(d_r\)，以及 \(l-1\) 到 \(root_{l-1}\) 的距离 \(d_{l-1}\)。

2. 如果两个根不同，说明这两个集合之前没有直接关系，现在可以通过这个等式把它们连起来。
   我们把一个根接到另一个根上，并设定新接上的根到另一个根的距离，使得等式成立。
   具体地，假设把 \(root_{l-1}\) 作为 \(root_r\) 的子节点，那么我们需要确定一个偏移量 \(w\)，使得：

\[ S_{root_{l-1}} \equiv w + S_{root_r} \pmod{p} \]

根据已知关系：

\[ S_r = d_r + S_{root_r},\quad S_{l-1} = d_{l-1} + S_{root_{l-1}} \]

代入 \(S_r = S_{l-1} + k\) 得：

\[ d_r + S_{root_r} = d_{l-1} + S_{root_{l-1}} + k \]

所以：

\[ S_{root_{l-1}} = d_r - d_{l-1} - k + S_{root_r} \]

因此偏移量 \(w = (d_r - d_{l-1} - k) \bmod p\)。
这样合并后，集合内所有节点的关系仍然保持。

3. 如果两个根相同，说明 \(r\) 和 \(l-1\) 已经在同一个集合里，它们之间的关系已经确定。
   我们可以通过它们到根的距离来检查这个新等式是否成立：

\[ (d_r - d_{l-1}) \bmod p \ \text{应该等于} \ k \]

如果相等，则一致；否则，这个询问就和之前的回答矛盾了。

细节

在合并时，只修改作为儿子的根节点 \(fx\) 的偏移量即可，不需要把这个根节点的整个子树全更新，因为后续还有find函数，即子树里的偏移量还是以 \(fa\) 作为标准的，直到后续要用find访问它时再直接路径压缩去更新即可