题解：P14417 [JOISC 2015] 防壁 / Walls

Larunatrecy · 2025-11-05 19:43:39 · 题解

首先，如果 P_i<P_{i+1}<P_{i+2}，那么从 i 到 i+2 的过程中一定会经过 i+1，直接删掉 i+1 即可（P_i>P_{i+1}>P_{i+2} 同理）。故接下来我们认为 P_i 这个序列是波浪状的。

记 L_i=B_i-A_i+1。

考虑如果 |P_i-P_{i+1}|\geq L_j 恒成立，则对于 P_i<P_{i+1} 一定是从 P_i+L_j-1 移动到 P_{i+1}（反过来同理），那么所有贡献都是固定的，形如 \sum|P_{i}-P_{i+1}-L_j| ，直接拆开计算即可。

否则，我们考虑 |P_i-P_{i+1}| 最小的一个 i（不妨认为 P_i<P_{i+1}），那么一定有 P_{i-1}>P_{i+1},P_{i+2}<P_i，可以发现此时从 P_{i-1} 到 P_{i+2} 的过程中左端点一定会经过 P_i，并且因为 |P_{i}-P_{i+1}|<L_j 故此时就覆盖了 P_{i+1}，因此这两个点都可以删掉。

当然在边界情况如 i-1 或者 i+2 不存在的情况要单独考虑一下，但都是可以删点的。

综上，我们将所有询问区间按照长度从小到大排序，用链表维护剩余的 P，用 set 维护最小的 |P_i-P_{i+1}| ，每次删掉直到满足 |P_i-P_{i+1}|\geq L_j，此时可以拆开 O(1) 计算，复杂度 O((N+M)\log M)。