题目理解

我们有 $N$ 个防壁，第 $i$ 个防壁初始位于水平区间 $[A_i, B_i]$，纵坐标为 $i$。有 $M$ 次攻击，第 $j$ 次攻击是从 $(P_j, N+1)$ 垂直向下射到 $(P_j, 0)$ 的镭射。

目标：通过左右移动防壁，使得每次攻击时，镭射都能穿过所有防壁（即每个防壁都要覆盖对应的 $P_j$），并最小化每个防壁的总移动次数。

移动规则：

• 可以在攻击前和攻击间隙任意移动
• 每次移动一个单位距离（左或右）
• 需要为所有 $M$ 次攻击都满足条件

关键观察

1. 问题转化

对于每个防壁 $i$，在攻击 $j$ 时，需要满足：

$$A_i \leq P_j \leq B_i$$

其中 $A_i, B_i$ 是防壁当前的位置。

由于我们可以移动防壁，这相当于：对于每个攻击 $P_j$，防壁 $i$ 必须移动到包含 $P_j$ 的位置。

2. 时间序列视角

将 $M$ 次攻击按时间顺序排列：$P_1, P_2, \dots, P_M$。

对于单个防壁，我们需要找到一序列位置 $[L_1, R_1], [L_2, R_2], \dots$（其中 $R_k - L_k = B_i - A_i$ 固定），使得：

• $P_k \in [L_k, R_k]$（覆盖当前攻击）
• 总移动距离 $\sum |L_{k+1} - L_k|$ 最小

3. 最优移动策略

对于单个防壁，最优策略是贪心的：

• 初始位置为 $[A_i, B_i]$
• 当遇到攻击 $P_j$ 时：
  • 如果 $P_j$ 在当前区间内，不移动
  • 如果 $P_j$ 在当前区间左侧，将区间左移直到包含 $P_j$
  • 如果 $P_j$ 在当前区间右侧，将区间右移直到包含 $P_j$

数学表达：设当前区间为 $[L, R]$，遇到攻击 $P$：

• 如果 $P < L$，移动距离 $L - P$，新区间 $[P, P + (R-L)]$
• 如果 $P > R$，移动距离 $P - R$，新区间 $[P - (R-L), P]$
• 否则移动距离 $0$，区间不变

算法思路

1. 直接模拟的复杂度

直接按时间顺序模拟每个防壁：

• 时间复杂度：$O(NM)$
• 对于 $N, M \leq 2\times 10^5$，这是不可接受的

2. 攻击点预处理

注意到攻击序列 $P_1, P_2, \dots, P_M$ 可能有很多重复或相近的值。

关键观察：防壁的移动只依赖于攻击点的极值，而不是所有攻击点。

更精确地说，对于固定长度的区间，移动距离只与攻击序列的下包络和上包络有关。

3. 单调栈优化

考虑攻击序列，我们只关心那些会"推动"防壁移动的点：

• 如果攻击点序列是单调的，防壁会一直向一个方向移动
• 方向改变只发生在序列的极值点

因此，我们可以用单调栈预处理攻击序列，提取出关键的"转折点"。

4. 提取关键点

对于每个防壁，我们关心的是那些会使其移动的攻击点。具体来说：

• 维护当前区间 $[L, R]$
• 扫描攻击序列，只记录那些导致区间移动的点
• 这些关键点构成一个序列，防壁在这个序列上的移动距离就是答案

5. 高效算法框架

1. 预处理攻击序列：用单调栈提取全局的关键转折点
2. 对每个防壁：在关键点序列上模拟，计算总移动距离
3. 复杂度：$O(N + M)$ 或 $O(N \log M)$

特殊情况分析

Subtask 1: $N = 1$

只有一个防壁，直接按时间顺序模拟即可：

• 维护当前区间位置
• 对每个攻击点，计算需要移动的距离
• 时间复杂度：$O(M)$

Subtask 2: $A_i = 0$

所有防壁左端点固定为 $0$，只有右端点可变。

• 防壁长度 $len_i = B_i - A_i + 1$
• 问题简化为：区间 $[0, R]$ 需要覆盖所有攻击点
• 移动策略：$R$ 至少要等于所有攻击点的最大值
• 但还要考虑区间长度限制，可能需要左右移动

完整解法核心

1. 关键点提取

对于攻击序列 $P_1, P_2, \dots, P_M$，我们提取：

• 下包络：单调递减序列中的关键点
• 上包络：单调递增序列中的关键点

这些关键点描述了防壁需要响应的重要位置变化。

2. 防壁移动计算

对于防壁 $i$，长度为 $L_i = B_i - A_i + 1$：

• 初始位置 $[A_i, A_i + L_i - 1]$
• 在关键点序列上模拟移动
• 总移动距离 = 在关键点序列上的曼哈顿距离

3. 几何解释

将问题看作：

• 每个防壁是一个长度为 $L_i$ 的滑动窗口
• 需要覆盖时间序列上的所有点
• 最小化窗口左端点的总变差

这类似于数据流中的滑动窗口问题，但窗口大小固定。

复杂度优化

1. 攻击序列压缩

使用单调栈在 $O(M)$ 时间内提取关键点：

• 维护一个栈，保存可能成为关键点的攻击
• 扫描过程中，根据单调性弹出不必要的点

2. 批量处理防壁

对所有防壁，在同一个关键点序列上计算：

• 按防壁长度排序
• 利用单调性批量计算移动距离
• 时间复杂度：$O(N \log N + M)$

总结

这道题的核心在于将看似复杂的移动问题转化为对攻击序列极值点的响应：

1. 问题本质：固定长度区间覆盖点序列的最小移动距离
2. 关键优化：攻击序列中只有极值点影响移动决策
3. 算法框架：单调栈提取关键点 + 在关键点上模拟移动
4. 复杂度：从 $O(NM)$ 优化到 $O(N \log N + M)$

通过深入分析问题结构，我们发现防壁的移动实际上只响应攻击序列的"包络线"，从而大幅降低了计算复杂度。