P12845 [蓝桥杯 2025 国 A] 连锁反应 题解

· · 题解

将炸弹按位置排序。先预处理出每个炸弹引爆后能影响到的最 左/右 侧的炸弹。以左侧为例：

设 g_i 表示第 i 个炸弹引爆后能同时引爆 i-g_i+1\sim i-1 个炸弹。转移分两种情况，如果 p_i-l_i>p_{i-1}，则 g_i=1；否则找到一个最小的 k 满足 k \ge p_i-l_i，则 g_i=\max_{k\le j\le i-1}(i-j+g_j)。

相同的，设 h_i 表示能引爆多少个右边的炸弹。

处理完左右两侧后，再做一个 DP。设 f_i 表示引爆 1\sim i 的所有炸弹的最少代价，转移时找到一个 j 满足 j+h_j-1 \ge i - g_i，则可以让 f_j+1 \to f_i。答案是 \min_{1\le i\le n,i+h_i-1=n}f_i。

所有的区间查询、单点修改都用线段树维护。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')   f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
struct SegmentTree {
    int mn[800005], mx[800005];
    void pushup(int p) {
        mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
        mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
        return;
    }
    void build(int p, int l, int r) {
        mn[p] = 1e15;
        mx[p] = -1e15;
        if(l == r) {
            return;
        }
        int mid = l + r >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        return;
    }
    void upd(int p, int l, int r, int k, int x) {
        if(l == r) {
            mn[p] = min(mn[p], x);
            mx[p] = max(mx[p], x);
            return;
        }
        int mid = l + r >> 1;
        if(k <= mid)    upd(p << 1, l, mid, k, x);
        else    upd(p << 1 | 1, mid + 1, r, k, x);
        pushup(p);
        return;
    }
    int querymn(int p, int l, int r, int L, int R) {
        if(R < L)   return 1e15;
        if(L <= l && r <= R) {
            return mn[p];
        }
        int mid = l + r >> 1;
        if(L > mid) return querymn(p << 1 | 1, mid + 1, r, L, R);
        if(R <= mid)    return querymn(p << 1, l, mid, L, R);
        return min(querymn(p << 1, l, mid, L, R), querymn(p << 1 | 1, mid + 1, r, L, R));
    }
    int querymx(int p, int l, int r, int L, int R) {
        if(R < L)   return 1e15;
        if(L <= l && r <= R) {
            return mx[p];
        }
        int mid = l + r >> 1;
        if(L > mid) return querymx(p << 1 | 1, mid + 1, r, L, R);
        if(R <= mid)    return querymx(p << 1, l, mid, L, R);
        return max(querymx(p << 1, l, mid, L, R), querymx(p << 1 | 1, mid + 1, r, L, R));
    }
}G, H, F;
struct node {
    int p, l, r;
}a[200005];
int n, g[200005], h[200005], f[200005], ans = 1e15;
inline int queryup(int x) {
    int l = 1, r = n, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(a[mid].p >= x) {
            res = mid;
            r = mid - 1;
        }
        else    l = mid + 1;
    }
    return res;
}
inline int querydn(int x) {
    int l = 1, r = n, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(a[mid].p <= x) {
            res = mid;
            l = mid + 1;
        }
        else    r = mid - 1;
    }
    return res;
}
bool cmp(node x, node y) {
    return x.p < y.p;
}
signed main() {
    n = read();
    for(int i = 1; i <= n; ++i) {
        a[i].p = read(); a[i].l = read(); a[i].r = read();
    }
    G.build(1, 1, n); H.build(1, 1, n); F.build(1, 0, n);
    g[0] = 0, h[0] = 0;
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; ++i) {
        int id = queryup(a[i].p - a[i].l);
        if(id == -1 || id >= i) g[i] = 1;
        else {
            g[i] = max(1ll, i - G.querymn(1, 1, n, id, i - 1));
        }
        G.upd(1, 1, n, i, i - g[i]);
    }
    for(int i = n; i >= 1; --i) {
        int id = querydn(a[i].p + a[i].r);
        if(id == -1 || id <= i) h[i] = 1;
        else {
            h[i] = max(1ll, H.querymx(1, 1, n, i + 1, id) - i);
        }
        H.upd(1, 1, n, i, h[i] + i);
    }
    f[0] = 0;
    F.upd(1, 0, n, 0, 0);
    for(int i = 1; i <= n; ++i) {
        f[i] = F.querymn(1, 0, n, i - g[i], n) + 1;
        F.upd(1, 0, n, i + h[i] - 1, f[i]);
    }
    for(int i = 1; i <= n; ++i) {
        if(i + h[i] - 1 == n) {
            ans = min(ans, f[i]);
        }
    }
    cout<<ans;
    return 0;
}