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

首先，如果 $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)$。