题解：P12845 [蓝桥杯 2025 国 A] 连锁反应【数据正确性待检验】

· · 题解

前言

正解感觉可以用贪心加区间和并之类的维护，但是赛场上想到了一种大力出奇迹的乱搞不需要动脑做法，特此记录。代码赛时是过了随机的对拍，本贴里的代码是赛后按照回忆重新打的，不保证正确，仅供参考。目前是只有 85 分，不知道哪里写挂了，希望大家一起帮忙看看。

更新:感谢@ran_qwq 的补充，之前错误的原因是只考虑了有意义的点的直接出点，而忽略了可能有意义点的直接出点是无意义，而无意义的出点又是有意义，这种间接到达的情况，hack数据如下:

input:
4
1 0 3
2 0 0
3 0 0
4 0 0
output:
1

现已能够通过所有数据。

题意

有 n 个炸弹，每个炸弹位置在 p[i], 爆炸后能连锁引爆范围在 p[i] - l[i] 到 p[i] + r[i] 范围内的其他炸弹。问至少有手动引爆多少个炸弹能使得所有炸弹都爆炸。 n \leq 2\times 10^5

O(n^2) 做法

首先考虑一下 O(n^2) 的做法怎么做。可以枚举每一对炸弹，预处理一下炸弹的连锁关系，如果 A 引爆，能导致 B 引爆，那么建一条 A 到 B 的有向边，就可以得到一张有向可能有环的图。对于这种有向有环图，思路都是先考虑假如没有环，对于一张有向无环图，答案是多少。模拟一下发现，对于所有入度为 0 的顶点，肯定都需要手动引爆一次，那么对于有入度的顶点，肯定都可以被入度那个顶点连锁引爆。答案就出来了，可以参照着下图理解一下这个过程，需要手动引爆的是编号为 1 和 4 的两个节点。

那么考虑有环的情况，自然想到了 tarjan 缩点，并且上面的结论对缩完点的图依然成立，只考虑一个环，都有入度，但是还需要手动引爆一次整个环都炸了。所以答案就是对图缩点后统计入度为 0 的顶点数， O(n^2) 的做法就出来了。

O(nlogn) 优化

那么很明显，上面做法的复杂度是卡在了建图的地方，需要 O(n^2) 的枚举点对。不过我们可以发现，一个点影响到的其他点显然是一段连续的按照 p[i] 排序的区间，启发我们使用线段树优化建图，实现点向区间连线。

需要注意的是，发现我们只会关注叶子节点能够到达的那部分线段树节点，而对再往上的部分不关心，直接用原始的线段树优化建图，也就是每个结点都往儿子节点建边，后续不方便统计出度之类的。因此，正确的统计方法(@ran_qwq指正)应该是，首先对于每个叶子，将它连向的线段树节点的整个子树标记(实现上可以先标记单个节点再遍历一次线段树下推这个标记)，然后将未标记的节点删去，有标记的那些节点进行缩点。之后对这个有标记的缩完点后的图直接统计入度为 0 的点数量即可。

这里拿样例为例，画一个图方便大家理解，首先对样例的点排序后重新编号，可以发现下面的覆盖关系:

用绿色的边表示线段树点向区间连边，红色的圈表示有标记的节点且缩点后的 SCC。对于红圈这个缩点后的标记子图，显然有2个入度为0的 SCC 即蓝星标记的那两个SCC，故答案为 2。得到下图所示： 可以这样具体实现：首先调用线段树的 get_leaf() 函数遍历一次，得到每个叶子节点的编号。之后叶子向线段树连边时，对应节点的 tag 数组置为1，之后再次遍历线段树调用 build() 函数，每个节点将 tag 标记下放到儿子，并且自身如果有标记的话才会向儿子连边。最后判断一下对于有标记的点再进行 tarjan 缩点，此时得到的 SCC 子图都是有标记的了，对这个子图统计入度为 0 的点数量即可。

代码

代码如下

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 8e5 + 10;
const int mod = 998244353;
struct tii {
    int a, b, c;
} arr[maxn];
bool cmp(tii x, tii y) {return x.a < y.a;}
int p[maxn], l[maxn], r[maxn];
vector<int> G[maxn];
int dfn[maxn], low[maxn], Cnt, instk[maxn], scc[maxn], cscc;
stack<int> stk;
void tarjan(int u) { //缩点板子
    low[u] = dfn[u] = ++Cnt;
    instk[u] = 1;
    stk.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (instk[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int top;
        cscc++;
        do {
            top = stk.top();
            stk.pop();
            instk[top] = 0;
            scc[top] = cscc;
        } while(top != u);
    }
}
int leaf[maxn], up, tag[maxn], ans, in[maxn];
struct SEG {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
    int t[maxn];
    void get_leaf(int rt, int l, int r) {
        if (l == r) {
            leaf[l] = rt;
            up = max(up, rt);
            return;
        }
        get_leaf(ls, l, mid), get_leaf(rs, mid + 1, r);
    }
    void build(int rt, int l, int r) {
        if (l == r) {
            return;
        }
        if (tag[rt])
            G[rt].push_back(ls), G[rt].push_back(rs);
        tag[ls] |= tag[rt], tag[rs] |= tag[rt];
        build(ls, l, mid), build(rs, mid + 1, r);
    }
    void Union(int rt, int l, int r, int p, int q, int id) {
        if (p > r || q < l) return;
        if (p <= l && r <= q) {
            G[leaf[id]].push_back(rt); //连边
            tag[rt] = 1;
            return;
        }
        Union(ls, l, mid, p, q, id), Union(rs, mid + 1, r, p, q, id);
    }
} seg;
void solve() {
    int n; cin >> n;
    seg.get_leaf(1, 1, n);
    for (int i = 1; i <= n; i++)
        cin >> arr[i].a >> arr[i].b >> arr[i].c;
    sort(arr + 1, arr + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        p[i] = arr[i].a, l[i] = arr[i].b, r[i] = arr[i].c;
    for (int i = 1; i <= n; i++) {
        int lo = p[i] - l[i], hi = p[i] + r[i];//寻找爆炸影响的 区间
        int lopos = lower_bound(p + 1, p + 1 + n, lo) - p;
        int hipos = upper_bound(p + 1, p + 1 + n, hi) - p - 1;
        if (lopos <= hipos) 
            seg.Union(1, 1, n, lopos, hipos, i); //建边
    }
    seg.build(1, 1, n);
    for (int i = 1; i <= up; i++)
        if (tag[i] && !dfn[i]) tarjan(i); //缩点
    for (int i = 1; i <= up; i++)
        for (auto v : G[i])
            if (!tag[i] || !tag[v]) continue; //跳过没有意义的点
            else if (scc[i] != scc[v]) {
                in[scc[v]]++; //统计入度
            }
    for (int i = 1; i <= cscc; i++)
        ans += in[i] == 0; //此时的所有 SCC 都已经是有意义的点浓缩后的，直接统计入度为 0 的即可
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}