P5025 [SNOI2017] 炸弹 题解

题意

link.

题解

一个好想一点的正解。

考虑到可能连锁爆炸，我们不能通过一个单纯的二分来解决问题。

考虑 dp。

记 \(f(i)\) 为第 \(i\) 个点爆炸，最远能引爆到哪个坐标小于它的点。

\(g(i)\) 为第 \(i\) 个点爆炸，最远能引爆到哪个坐标大于它的点。

我们以 \(f\) 为例，\(g\) 可以通过同样的方法求得。

对于每一个 \(i\)，二分出一个最小的 \(l\) 满足 \(\lvert x_l - x_i \rvert \le r_i\)，此时区间 \(\left [ l, i - 1 \right ]\) 就是 \(i\) 通过一次爆炸能爆到的。

但是可以连锁爆炸，所以我们需要选出一个 \(t \in \left [ l, i - 1 \right ]\) 使得 \(f(t)\) 最小。

此时就可以转移了：

但找出 \(t\) 的复杂度是 \(\mathcal O(n)\) 的，总时间复杂度是 \(\mathcal O (n^2 + n \log n)\) 的，这样就可以光荣的获得 \(55\) 分了。

考虑开一棵线段树，维护 \(x_i - r_i\) 的最小值和最小值的编号。

因为满足 \(f(t)\) 最小的 \(t\) 也一定满足 \(x_i - r_i\) 最小，反之同理。

此时只需要查询一下区间 \(\left [ l, i - 1 \right ]\) 最小值编号即可作为 \(t\) 转移了。

\(g\) 只需要开一棵最大值线段树即可。

然后你就会发现它错了（貌似样例都过不了）。

我们不能把思维固定在 \(f\) 转移 \(f\)，\(g\) 转移 \(g\) 上。

有可能我们先爆炸炸到 \(i\) 右边，然后通过引爆 \(i\) 右边一枚非常强悍的炸弹然后再引爆到左边。

所以要反着再转移一次。

然后你就会发现它又错了（貌似会错第二个点）。

因为我们通过走右边到达了左边，此时我们还需要再走一次左边，因为走过来不一定是最小的（真烦）。

右边同理。

所以重复一边上文的过程即可。

但值得庆幸的是，这么就能过了，因为此时已经把所有方案考虑完了。

时间复杂度：\(\mathcal O (n \log n)\)，带一点线段树的并不小的常数。

namespace zqh {
const int N = 5e5 + 5;

int n;
struct bomb {  // 炸弹结构体
    int x, r;
} a[N];
int dpl[N], dpr[N];
struct segment {    // 线段
    int mx, mx_id;  // 最大值，最大值编号，下同
    int mn, mn_id;
};

struct segment_tree {  // 线段树
#define ls (id << 1)
#define rs (id << 1 | 1)
    segment seg[N << 2];
    void pushup(int id) {
        if (seg[ls].mn < seg[rs].mn) {
            seg[id].mn = seg[ls].mn;
            seg[id].mn_id = seg[ls].mn_id;
        } else {
            seg[id].mn = seg[rs].mn;
            seg[id].mn_id = seg[rs].mn_id;
        }
        if (seg[ls].mx > seg[rs].mx) {
            seg[id].mx = seg[ls].mx;
            seg[id].mx_id = seg[ls].mx_id;
        } else {
            seg[id].mx = seg[rs].mx;
            seg[id].mx_id = seg[rs].mx_id;
        }
    }
    void build(int id, int lft, int rht) {  // 建树
        seg[id].mn = LLONG_MAX;
        seg[id].mx = LLONG_MIN;
        if (lft == rht) {
            seg[id].mn_id = seg[id].mx_id = lft;
            seg[id].mn = a[lft].x - a[lft].r;
            seg[id].mx = a[lft].x + a[lft].r;
            return;
        }
        int mid = (lft + rht) / 2;
        build(ls, lft, mid);
        build(rs, mid + 1, rht);
        pushup(id);
    }
    segment query(int id, int lft, int rht, int l, int r) {
        if (rht < l || r < lft)
            return {LLONG_MIN, -1, LLONG_MAX, -1};
        if (l <= lft && rht <= r)
            return seg[id];
        int mid = (lft + rht) / 2;
        segment t1 = query(ls, lft, mid, l, r),
                t2 = query(rs, mid + 1, rht, l, r), ret;
        if (t1.mn < t2.mn) {
            ret.mn = t1.mn;
            ret.mn_id = t1.mn_id;
        } else {
            ret.mn = t2.mn;
            ret.mn_id = t2.mn_id;
        }
        if (t1.mx > t2.mx) {
            ret.mx = t1.mx;
            ret.mx_id = t1.mx_id;
        } else {
            ret.mx = t2.mx;
            ret.mx_id = t2.mx_id;
        }
        return ret;
    }
} st;

void dp() {                         // 跑一次 dp
    for (int i = 2; i <= n; i++) {  // 算 f（直接走左边）
        int l = 1, r = i - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (abs(a[mid].x - a[i].x) <= a[i].r) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (ans == -1)
            continue;
        segment t = st.query(1, 1, n, ans, i - 1);
        dpl[i] = min(dpl[i],
                     min((dpl[t.mn_id] == -1 ? LLONG_MAX : dpl[t.mn_id]), ans));
    }
    for (int i = n - 1; i >= 1; i--) {  // 算 g（直接走右边）
        int l = i + 1, r = n, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (abs(a[mid].x - a[i].x) <= a[i].r) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (ans == -1)
            continue;
        segment t = st.query(1, 1, n, i + 1, ans);
        dpr[i] = max(dpr[i],
                     max((dpr[t.mx_id] == -1 ? LLONG_MIN : dpr[t.mx_id]), ans));
    }
    for (int i = 2; i <= n; i++) {  // 算 g（走左边再走右边）
        int l = 1, r = i - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (abs(a[mid].x - a[i].x) <= a[i].r) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (ans == -1)
            continue;
        segment t = st.query(1, 1, n, ans, i - 1);
        dpr[i] = max(dpr[i],
                     max((dpr[t.mx_id] == -1 ? LLONG_MIN : dpr[t.mx_id]), ans));
    }
    for (int i = n - 1; i >= 1; i--) {  // 算 f（走右边再走左边）
        int l = i + 1, r = n, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (abs(a[mid].x - a[i].x) <= a[i].r) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (ans == -1)
            continue;
        segment t = st.query(1, 1, n, i + 1, ans);
        dpl[i] = min(dpl[i],
                     min((dpl[t.mn_id] == -1 ? LLONG_MAX : dpl[t.mn_id]), ans));
    }
}

void init() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].r;
        dpl[i] = dpr[i] = i;
    }
}

void solve() {
    st.build(1, 1, n);  // 建树
    dp();               // 跑两次
    dp();
    int ans = 0;
    for (int i = 1; i <= n; i++) {  // 统计答案
        //			cout << dpl[i] << " " << dpr[i] << endl;
        if (dpl[i] == -1 && dpr[i] == -1) {
            ans = 1LL * (ans + 1 * i) % mod;
            continue;
        }
        if (dpl[i] == -1) {
            ans = (ans + 1LL * (1LL * (dpr[i] - i + 1) % mod * i) % mod) % mod;
            continue;
        }
        if (dpr[i] == -1) {
            ans = (ans + 1LL * (1LL * (i - dpl[i] + 1) % mod * i) % mod) % mod;
            continue;
        }
        ans = (ans + 1LL * (1LL * (dpr[i] - dpl[i] + 1) % mod * i) % mod) % mod;
    }
    cout << ans;
}

void main() {
    init();
    solve();
}
}  // namespace zqh

谨此，纪念我这道自己想、自己调、并且差点赛切的紫题（赛时 \(92\) 分）。