题解 P5025【[SNOI2017]炸弹】

Krystallos · 2020-11-17 21:58:15 · 题解

提供一种短小精悍的 O(n) 解法
P.S. 下文中 r 会表示答案区间，原题的爆炸半径 r 我这里叫 range
首先有一个结论：无论如何引爆，如果炸弹 l 和 r 被引爆了 (l \leq r)，那么任何炸弹 p \in [l, r] 都会被引爆。那么考虑维护最开始引爆炸弹 i 后，所有最后被引爆的炸弹区间 [l_i, r_i]。
先把所有 [l_i, r_i] 初始化为 [i, i]，然后令 i 从 2 开始，到 n 结束，执行以下操作：

• 判断自己能否引爆炸弹 l_i - 1，如果不能或者 l_i = 1，终止操作
• 比较自己的爆炸右边界 (x_i + range_i) 与 l_i - 1 的爆炸右边界 (x_{l_i - 1} + range_{l_i - 1})，如果后者更大那么用后者减去 x_i 的值来更新 range_i
• 将 l_i 更新为 l_{l_i - 1}，并返回第一个操作

这样一轮算下来之后我们就可以计算出只往左爆炸能够到达的边界 l_i，时间复杂度是线性的

for (int i = 2; i <= n; i++) {
    while (l[i] > 1 && a[i] - a[l[i] - 1] <= range[i]) {
        range[i] = std::max(range[i], range[l[i] - 1] - (a[i] - a[l[i] - 1]));
        l[i] = l[l[i] - 1];
    }
}

简单证一下复杂度，外层循环显然是线性的；内层循环中，会存在某一个炸弹 p 它往前炸到了很多以前并不关联的炸弹的情况。看起来这个循环的极限复杂度很高，但是一旦这些炸弹纳入了当前炸弹 p 的影响范围内后，后续炸弹与这段炸弹的关联无非就是都能炸到，或者都不能炸到。不可能只炸一部分，因为这段炸弹的最右侧是 p，炸到一部分就炸到了 p，炸到了 p 就能炸完这一整段。所以这段炸弹以后的复杂度贡献就几乎没有了。更何况如果后续有炸弹能炸完这一段炸弹，那这段炸弹就被划进一个更大的炸弹爆炸段了。所以这两个循环的总复杂度是 O(n)。
类似的，我们可以从右往左扫一遍来计算答案右端点 r_i。注意，刚才我只说了求出来的 l_i 是只往左爆炸的答案，这时我们也需要顺带把先往右炸到一个大炸弹再往左炸的答案更新了。流程是这样：

• 判断自己能否引爆炸弹 r_i + 1，如果不能或者 r_i = n，终止操作
• 比较自己的爆炸左端点 l_i 与先往右炸再往左炸的答案 l_{r_i + 1}，如果后者更小则用后者更新前者
• 将 r_i 更新为 r_{r_i + 1}，返回第一个操作

这样我们就可以算完整个答案了。复杂度与上面一致，为线性。

for (int i = n - 1; i >= 1; i--) {
    while (r[i] < n && a[r[i] + 1] - a[i] <= range[i]) {
        l[i] = std::min(l[i], l[r[i] + 1]);
        r[i] = r[r[i] + 1];
    }
}

这里的 range 已经是更新过的 range 了，我们在最开始从左往右扫的时候已经把 range 设成了允许先炸左边再炸右边能达到的边界，所以先往左炸再往右炸的答案是已经考虑了的。至于更新 l_i 的操作就是去看右边自己能炸到的炸弹能不能往左再炸了。
最后引爆炸弹 i 的答案就是 r_i - l_i + 1 了。因为最后爆掉的肯定是连续一段。
完整代码：

#include <cstdio>
#include <iostream>
const int nn = 5e5 + 5, mod = 1e9 + 7;
int n, l[nn], r[nn];
long long ans, a[nn], range[nn];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld", a + i, range + i);
        l[i] = r[i] = i;
    }
    for (int i = 2; i <= n; i++) {
        while (l[i] > 1 && a[i] - a[l[i] - 1] <= range[i]) {
            range[i] = std::max(range[i], range[l[i] - 1] - (a[i] - a[l[i] - 1]));
            l[i] = l[l[i] - 1];
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        while (r[i] < n && a[r[i] + 1] - a[i] <= range[i]) {
            l[i] = std::min(l[i], l[r[i] + 1]);
            r[i] = r[r[i] + 1];
        }
    }
    for (int i = 1; i <= n; i++)
        ans = (ans + 1ll * i * (r[i] - l[i] + 1)) % mod;
    printf("%lld\n", ans);
    return 0;
}

效率没的说，最优解榜一就是这个代码
或者说其实这玩意的正确性和效率是假的？（欢迎来 Hack