【PA 2020】Miny

P9100 [PA 2020] Miny - 洛谷

给出每一个炸弹 $i$ 的位置 $a_i$ 和爆炸半径 $r_i$，每次爆炸都会使得 $[a_i - r_i, a_i + r_i]$ 范围内的炸弹爆炸，发生连锁反应。起爆的炸弹集合不定，问你最终的局面的方案数。

$1 \le n \le 3 \times 10 ^ 5, 0 \le a_i, r_i \le 10 ^ {18}$。

我们考虑 dp 的转移。

发现其实我们并不能得到一个很好的没有后效性的东西。

我们不妨发挥人类智慧，设计一个好的的 dp 状态。

我们设 $dp_i$ 表示，前 $i$ 个炸弹，以 $i$ 结尾，且钦定 $i$ 不爆炸的方案数。那么我们枚举 $j < i$ 进行转移，当且仅当 $[j + 1, i -1]$ 这部分的炸弹爆炸不会波及到 $i$ 和 $j$ 这样才能满足我们设定的不爆炸的钦定。 为了更好的判断是否波及，我们设 $L_i$ 表示左边能引爆 $i$ 的最大的炸弹，$R_i$ 表示右边能引爆 $i$ 的最小的炸弹。换言之就是最近且能引爆 $i$ 的。 这个过程我们可以用单调栈维护，我们可以通过单调栈，扫描两次，第一次求 $L$，第二次求 $R$，那么由于随着下标的增长，$a_i$ 是不断增加的，我们要想知道 $i$ 左边的第一个能引爆 $i$ 的，我们需要在单调栈中维护能覆盖 $a_i$ 的，最大的下标。若是当前的栈顶无法满足，就弹出，找前面的是否有能满足的。 对于这样的操作，我们再从后往前扫一次即可得到 $R$。

那么我们的 dp 可以转化为：

$$ dp_i = \min_{j < i \text{ and } (L_i \le j) \text{ and } (R_j \ge i)}(dp_i = dp_j + dp_i) $$

对于这个操作实际上是 $n ^ 2$ 的，我们考虑优化。

我们不难发现，满足条件 $L_i \le j$ 的序列，实际上下标直接就可以从 $L_i$ 开始一直到 $i$。

换言之，我们答案就是 $j \in [L_i, i - 1] \text{ and } R_j \ge i$ 的 $\sum dp_j$。

对于这样的询问，我们难免会想到在处理完当前的 $i$ 之后，把 $dp_i$ 插入到树状数组中，然后问 $[L_i, i - 1]$ 的时候，直接用树状数组做前缀和差分即可。

但是问题就在于，我们在询问 $L$ 的时候，插入的 $dp_i$ 实际上是只有 $[0, L]$ 的部分的 $R_j \ge i$ 的部分，可是留到最后算是会出问题的。

这个时候就可以用两种方式解决这个问题。

第一种方式是主席树，我们考虑把不同版本存下来，问 dp 的时候，只需要找到 $L_i - 1$ 的版本和 $i - 1$ 的版本即可。

第二种方式，我们把需要用到的询问离线下来，每次做完当前 $i$ 的操作之后，把挂在 $i$ 上的询问的答案都计算出来。

时间复杂度 $\mathcal{O}(n \log n)$。