题解：P16435 [APIO 2026 中国赛区] 集宝
nullptr_qwq_
·
·
题解
你怎么知道我有 A,C 性质的二十昏没调出来？
令 S_i 表示 (a_i,d_i) 所描述的邻域。注意到不会做多余的移动，因此每步如果已经在 S_i 中那么不动，否则向 S_i 移动若干步直到到邻域的边界上，由此有直接贪心的 \mathcal O(nq) 做法。
- 可以酌情跳过性质 B,C 的做法。虽然这两个部分对正解的相关性还是挺大的。
【性质 B】
以直径中点为根，那么每次邻域是一个含根的连通块。最终 x 只会向根移动若干步到 y，那么 y 一定是 S_l\sim S_r 的交集中的元素。而邻域交邻域还是邻域（中心可能是一条边的中点），因此求 S_l\sim S_r 的交集是可以处理的。只需要实现邻域交邻域的过程，需要支持快速查 \text{LCA} 以及 k 级祖先来做到 \mathcal O(1) 查询，后者可以长剖后对每个长链保留向上 2^h 个点。再使用 ST 表合并即可。
最终答案就是 x\sim y 简单路径的边数。
【性质 C】
用一个扫描线的思路，初始在 1\sim n 上各放棋子，显然有棋子的连通块是一个邻域 cur，每次扫到 S_i 时：
- 若 cur\cap S_i\ne\varnothing，则 cur\to cur\cap S_i，原先不在 S_i 的位置会移动到 S_i 的边界上，可以暴力处理这些棋子然后合并到移动后边界位置的棋子上，在此过程计算一下移动的代价，这样操作会少一个棋子，均摊次数是 \mathcal O(n) 的。
- 否则 cur\cap S_i=\varnothing，此时 cur 中的所有元素会合并到一个单点上（S_i 离 cur 最近的节点），同理可以暴力考虑每个棋子并合并。
对这个过程可持久化即可，时间复杂度 \mathcal O(n\log n)。缩棋子可以用线段树维护直径或者点分树，难写的，正解也不需要写这玩意。
【正解】
结合性质 B,C，找到极长的 S_l\cap \cdots\cap S_k 非空，得到邻域 T，x 移动过来的路径一定是简单路径，这里计算一下 x 到 T 要移动的边数即可，然而到 S_{k+1} 时就会被迫移动过去。
对于 k+1\sim r：令 f(x,l,r) 表示询问的东西，容易发现这个询问在这段时间的贡献是 f(1,1,r)-f(1,1,k+1)，这是因为由于交集为空，此时起点是不重要的，所有点都“重置”掉，是等价的。手动算一下 l 时间和 k\to k+1 时间的贡献即可。
最终只需要支持快速求区间邻域交以及算 x=1,l=1 的所有 f(1,1,r)。双指针预处理对于所有 l，最大的 r 使得 S_l 交到 S_r 非空即可。
时间复杂度 \mathcal O(n\log n)。
update：如果可以离线，并且套用线性预处理 k 级祖先和 \text{LCA}，总复杂度 \mathcal O(n\alpha(n))，瓶颈在于区间信息查询。