[数据结构与算法]P5025 [SNOI2017] 线段树优化建图 + SCC 分解 + 拓扑序

题意

传送门 P5025 [SNOI2017]炸弹

题解

若炸弹 $v$ 可以引爆 $u$，则 $v\to u$ 连一条边。炸弹 $v$ 可引爆的炸弹数为 $v$ 可达的节点数，这可以通过分解强连通分量后，进行拓扑序递推得到。难以直接求解任意拓扑序上节点的可达节点数 ，但此处节点可达集合满足连续性，那么维护可达的左右界集即可。

上述做法时空复杂度均为 $O(n^2)$。考虑线段树优化建图，那么 $v\to [l,r]$ 连边数为 $O(\log n)$。总时间复杂度 $O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 5E5 + 5, SZ = 1 << 20, MOD = 1E9 + 7;
int N, in[MAXN];
ll X[MAXN], L[MAXN], R[MAXN], sx[MAXN];
vector<int> G[SZ], rG[SZ], nG[SZ];

void add_edge(int u, int v) { G[u].pb(v), rG[v].pb(u); }

struct ST
{
    void init(int k = 0, int l = 0, int r = N)
    {
        if (r - l == 1)
        {
            in[l] = k;
            return;
        }
        int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
        init(chl, l, m), init(chr, m, r);
        add_edge(k, chl), add_edge(k, chr);
    }
    void change(int a, int b, int v, int k = 0, int l = 0, int r = N)
    {
        if (r <= a || b <= l)
            return;
        if (a <= l && r <= b)
        {
            add_edge(in[v], k);
            return;
        }
        int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
        change(a, b, v, chl, l, m), change(a, b, v, chr, m, r);
    }
} itr;

int idx[SZ], lb[SZ], ub[SZ];
int _lb[SZ], _ub[SZ], deg[SZ];
vector<int> vs;
bool used[SZ];

void dfs(int v)
{
    used[v] = 1;
    for (int u : G[v])
        if (!used[u])
            dfs(u);
    vs.pb(v);
}

void rdfs(int v, int k, int &l, int &r)
{
    used[v] = 1, idx[v] = k;
    l = min(l, lb[v]), r = max(r, ub[v]);
    for (int u : rG[v])
        if (!used[u])
            rdfs(u, k, l, r);
}

int find_scc()
{
    int n = SZ;
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int i = 0; i < n; ++i)
        if (!used[i])
            dfs(i);
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = (int)vs.size() - 1; i >= 0; --i)
        if (!used[vs[i]])
            rdfs(vs[i], k, _lb[k], _ub[k]), ++k;
    return k;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        ll r;
        cin >> X[i] >> r;
        sx[i] = X[i];
        L[i] = X[i] - r, R[i] = X[i] + r;
    }
    for (int i = 0; i < N; ++i)
    {
        X[i] = lower_bound(sx, sx + N, X[i]) - sx;
        L[i] = lower_bound(sx, sx + N, L[i]) - sx;
        R[i] = upper_bound(sx, sx + N, R[i]) - sx - 1;
    }
    itr.init();
    memset(lb, 0x3f, sizeof(lb)), memset(ub, 0xc0, sizeof(ub));
    memset(_lb, 0x3f, sizeof(_lb)), memset(_ub, 0xc0, sizeof(_ub));
    for (int i = 0; i < N; ++i)
    {
        int v = in[X[i]];
        lb[v] = L[i], ub[v] = R[i];
        itr.change(L[i], R[i] + 1, X[i]);
    }
    int n = find_scc();
    for (int v = 0; v < SZ; ++v)
        for (int u : G[v])
            if (idx[v] != idx[u])
                nG[idx[u]].pb(idx[v]), ++deg[idx[v]];
    queue<int> q;
    for (int v = 0; v < n; ++v)
        if (!deg[v])
            q.push(v);
    while (q.size())
    {
        int v = q.front();
        q.pop();
        for (int u : nG[v])
        {
            _lb[u] = min(_lb[u], _lb[v]);
            _ub[u] = max(_ub[u], _ub[v]);
            if (!--deg[u])
                q.push(u);
        }
    }
    ll res = 0;
    for (int i = 0; i < N; ++i)
    {
        int v = idx[in[X[i]]];
        int l = _lb[v], r = _ub[v];
        res = (res + (ll)(i + 1) * (r - l + 1)) % MOD;
    }
    cout << res << '\n';
    return 0;
}