[SNOI2017] 炸弹

形式化题目

直线上有 $n$ 个炸弹，第 $i$ 个炸弹坐标为 $x_i$ 、爆炸半径为 $r_i$ ，满足 $x_1 < x_2 < \cdots < x_n$ 。

若炸弹 $i$ 爆炸且 $|x_j - x_i| \leqslant r_i$ ，则炸弹 $j$ 也会被引爆；被引爆的炸弹再按同一规则继续引爆其他炸弹。

记 $S_i$ 为「先引爆第 $i$ 个炸弹后，最终被引爆的炸弹集合」（包含 $i$ 自身），求

\sum_{i=1}^{n} i \cdot |S_i| \bmod (10^9+7).

解法总览

本题有两种完全不同的做法，差别不在常数优化，而在要不要把引爆关系建成图。

解法一（正式主解，main.cpp）忠实于「连锁引爆 = 有向图可达性」这个原始模型，用线段树把「点向一段区间连边」压成 $O(\log n)$ 条，再 Tarjan 缩点、在 DAG 上传播区间端点。它需要显式建出 $10^6$ 量级的图，实现量大，但建模直白，是这类题的标准套路。
解法二（alt1.cpp）根本不建图，只利用「引爆集合必为连续下标区间」这一条性质，对每个炸弹维护当前闭包块的左右端点和右向射程，先从左往右做一遍只向左的闭包合并，再从右往左做一遍只向右的吸收。整体 $O(n)$ ，代码二十余行。

两者是并列关系：解法二不是解法一的优化，它连图都没有。选择上，若只是想通过本题，解法二更快更短；若想学习「区间连边」这一类通用技巧，解法一才是可迁移的那一套。

解法	核心观察	复杂度	适用场景	对应代码
一：线段树优化建图 + Tarjan	引爆关系是点向连续区间连边，可达集合是连续区间	$O(n\log n)$ 时间， $O(n\log n)$ 空间	通用套路，可迁移到任意「点向区间连边」的图论题	`main.cpp`
二：不建图的双向扫描	引爆集合是连续区间，且左侧闭包吸收完毕后右向射程仍然可用	$O(n)$ 时间， $O(n)$ 空间	本题及同型「一维连锁引爆」题；依赖集合的区间性	`alt1.cpp`

下表是同一台机器上的实测值（ $n=5\times10^5$ ，八组极端数据取最慢一组），可与上面的复杂度声明对照：

解法	最慢一组 CPU	峰值内存
一：线段树优化建图 + Tarjan	680 ms	73 MiB
二：不建图的双向扫描	51 ms	32 MiB

解法一：线段树优化建图 + Tarjan 缩点

思路

第一步：把引爆关系看成有向图的可达性

建一张有向图：炸弹是点，若 $|x_j-x_i|\leqslant r_i$ 就从 $i$ 向 $j$ 连边。那么 $S_i$ 就是 $i$ 在这张图上能到达的点集， $|S_i|$ 就是可达点数。

这个模型完全正确，但直接建图的边数是

\sum_{i=1}^{n} |\{j : lo_i \leqslant j \leqslant hi_i\}| = O(n^2),

最坏（每个炸弹半径都覆盖整条直线）是 $n^2$ 条边。而本题 $n$ 最大 $5\times 10^5$ ， $n^2 = 2.5\times 10^{11}$ ，无论时间还是空间都不可能承受（按定义逐点搜索更要 $O(n^3)$ ，只能过 $n \leqslant 100$ 的第一档，本文不再单独展开）。所以瓶颈很清楚：不是可达性模型有问题，而是「点向一个区间连边」这件事的表示方式太浪费。

第二步：直接引爆的炸弹是一段连续区间

因为 $x$ 严格递增，集合 $\{j : |x_j - x_i| \leqslant r_i\}$ 就是坐标落在 $[x_i-r_i,\; x_i+r_i]$ 里的那些点，下标天然连续：

lo_i = \min\{j : x_j \geqslant x_i - r_i\}, \qquad hi_i = \max\{j : x_j \leqslant x_i + r_i\}.

两次二分即可，单点 $O(\log n)$ 。这一步把「向若干点连边」变成了「向一段下标区间连边」。

以样例为例（ $n=4$ ）：

$i$	$x_i$	$r_i$	直接覆盖的坐标	直接引爆的下标区间
1	1	1	$[0,2]$	$[1,1]$
2	5	1	$[4,6]$	$[2,3]$
3	6	5	$[1,11]$	$[1,3]$
4	15	15	$[0,30]$	$[1,4]$

表格第 5 列就是把「 $i$ 能炸谁」压缩成的一个区间。

第三步：区间连边用线段树压缩

把炸弹当作一棵线段树的叶子（取 $m = 2^{\lceil\log_2 n\rceil}$ ，炸弹 $i$ 的叶子编号为 $m+i-1$ ），并让每个内部节点向自己的两个儿子连边。这样「走到某个节点」就等价于「走到它覆盖的所有叶子」。

下面画的是 $n=8$ 的线段树结构，括号里写该节点覆盖的炸弹下标范围，底层 8 个叶子就是 8 个炸弹：

text

1
2
3
4
5
6
7
8                     1  [1,8]
                  /            \
            2 [1,4]              3 [5,8]
            /      \             /      \
      4 [1,2]    5 [3,4]    6 [5,6]    7 [7,8]
       /   \      /   \      /   \      /   \
      8     9   10    11   12    13   14    15     ← 叶子 = 炸弹 1..8
     [1]   [2]  [3]   [4]  [5]   [6]  [7]   [8]

于是假若某个炸弹要引爆下标区间 $[1,6]$ ，它不需要连 6 条边，只要连两条：叶子 8 → 节点 2（覆盖 $[1,4]$ ）和叶子 8 → 节点 6（覆盖 $[5,6]$ ）。一般地，任意区间都能分解成 $O(\log n)$ 个规范节点，这就是线段树区间查询的经典结论。

建完的图满足：从叶子 $i$ 能走到叶子 $j$ ，当且仅当 $j \in [lo_i, hi_i]$ 。可达关系与原图一模一样，边数却从 $O(n^2)$ 降到 $O(n\log n)$ 。

第四步：一个关键性质——可达集合仍是区间

线段树只解决了「边太多」，还有第二个坑：即使有了 DAG，也不能直接 dp[u] = sum(dp[v]) 去统计可达点数，因为同一个炸弹可能被多条路径到达，会被重复计数。

救命的性质是： $S_i$ 一定是下标连续的一段。

直观理解：从 $\{i\}$ 出发，每一轮把「已引爆集合里每个炸弹直接引爆的区间」并进来。每一步并进来的都是一整段区间，并且都跟当前集合相交（因为炸弹 $u$ 直接引爆的区间必然包含 $u$ 自己），所以集合始终是一个区间，只会向左右两端扩张。既然最终结果是一段连续下标，就只需要记最左端 $L_i$ 与最右端 $R_i$ ， $|S_i| = R_i - L_i + 1$ 。

这一步的意义：把「可达集合」这个指数级对象降维成两个数，而且合并时用 $\min/\max$ 天然不会重复计数。

用样例验证这个性质，从各点出发做区间扩张：

起点	初始区间	扩张过程	最终 $[L,R]$	$\lvert S_i\rvert$
1	$[1,1]$	1 只覆盖 $[1,1]$ ，不动	$[1,1]$	1
2	$[2,2]$	2 覆盖 $[2,3]$ → $[2,3]$ ；3 覆盖 $[1,3]$ → $[1,3]$ ；1 覆盖 $[1,1]$ ，不动	$[1,3]$	3
3	$[3,3]$	3 覆盖 $[1,3]$ → $[1,3]$ ；1、2 都不再扩张	$[1,3]$	3
4	$[4,4]$	4 覆盖 $[1,4]$ → $[1,4]$ ；1、2、3 都不再扩张	$[1,4]$	4

答案是 $1\cdot 1 + 2\cdot 3 + 3\cdot 3 + 4\cdot 4 = 1+6+9+16 = 32$ ，与样例一致。

第五步：Tarjan 缩点，在 DAG 上传播区间端点

互相可达的点集合必然相同，所以先把图缩成 SCC。缩点后得到 DAG，每个 SCC 维护一对 $(min, max)$ ：

初值：该 SCC 内部包含的炸弹下标的最左、最右值（线段树内部节点不是炸弹，不能计入）；
转移：按拓扑序扫，对每条跨 SCC 的出边 $u \to v$ ，用 $(min_{scc[v]}, max_{scc[v]})$ 去更新 $u$ 所在 SCC 的端点。

这里有个漂亮的实现细节：Tarjan 的 SCC 弹出顺序本身就是拓扑序。若存在边 $A \to B$ 且 $A,B$ 属于不同 SCC，则 $B$ 必然先于 $A$ 被弹出，即 scc[A] > scc[B]。所以只要按编号 $1 \to scc\_cnt$ 扫一遍，就能保证所有后继 SCC 都已算好，不需要再排一次拓扑序，也不需要建反图。

最后对每个炸弹 $i$ ，答案累加 $i \cdot (max - min + 1)$ 并取模。

和代码的对应：上面的 $[lo_i, hi_i]$ 就是 lo[i] / hi[i]（手写二分，返回值域是 $[1,n+1]$ 与 $[0,n]$ ，空区间也能正确表示）；每个 SCC 的两个端点就是 scc_min[id] / scc_max[id]（初值分别取 INT_MAX 和 0，于是只含线段树节点的 SCC 自然算出空区间）； SCC 的成员靠 scc_begin[] + pop_order[] 两数组定位，避免每个 SCC 再开一个 vector。

第六步：为什么 Tarjan 必须写成迭代

按题目规模，图里可以同时存在一条 $5\times10^5$ 长的炸弹引爆链（每个炸弹只炸下一个）和在此基础上更深的结构。实测（ $n=5\times10^5$ 、相邻坐标间距 2、半径 2）递归 Tarjan 的最大递归深度达 750017 层；用 roj-local-judge-lite --stack 逐档实测，需要约 60MiB 栈才不崩溃（--stack 8/16/32/48/56 全部 RE signal 11），紧贴判题器 64MiB 的默认栈且毫无余量。本机 shell 默认栈只有 8MiB，直接跑必然段错误。

因此本题的 Tarjan 用显式栈迭代实现。这是「规模确定超出栈容量」的强制例外，代价是代码要把「进入节点 / 回溯更新 low / 出栈判 SCC」三个阶段手工分开写。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 13:34
 * update_at: 2026-10-23 15:05
 */
// main.cpp：线段树优化建图 + Tarjan 缩点 + DAG 上传递可达区间。
// 关于栈：图中存在一条 n = 5e5 长的炸弹引爆链，实测递归 Tarjan 的最大递归深度达 750017 层，
// 用 roj-local-judge-lite --stack 实测要 60MB 栈才不崩（--stack 8/16/32/48/56 全部 RE signal 11），
// 紧贴判题器 64MB 默认栈、没有任何余量，因此本题的 Tarjan 必须用显式栈迭代实现。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 500005;   // 炸弹个数上限
const int MAXM = 1 << 20;  // 线段树节点编号上界（n = 5e5 时 m = 2^19 = 524288）
const ll MOD = 1000000007;

int n;                   // 炸弹个数
int m;                   // 不小于 n 的最小 2 的幂，炸弹 i 的叶子编号为 m + i - 1
ll x[MAXN];              // x[i]：第 i 个炸弹的坐标（严格递增）
ll r[MAXN];              // r[i]：第 i 个炸弹的爆炸半径
int lo[MAXN], hi[MAXN];  // [lo[i], hi[i]]：第 i 个炸弹直接引爆的炸弹下标区间
int node_cnt;            // 图中节点总数 = m + n - 1

// 图用 CSR（压缩稀疏行）存储：节点 u 的出边是 adj_to[adj_start[u] .. adj_start[u+1])。
// 本题边数接近 1e7，链式前向星要 3 个 int 数组约 120MB，CSR 只要 2 个数组且遍历更快。
vector<int> adj_start;
vector<int> adj_to;
int edge_cnt;  // 已写入 adj_to 的边数

// 炸弹 i 在图中对应的叶子节点编号
int leaf_of(int bomb) {
    return m + bomb - 1;
}

// 输入最多 1e6 个 64 位整数（约 20MB 文本），一次性读入再按下标解析，比 scanf 快一倍以上
vector<char> input_buf;
size_t input_pos;

void load_input() {
    size_t len = 0;
    input_buf.resize(1 << 20);
    while (true) {
        if (len == input_buf.size()) input_buf.resize(input_buf.size() * 2);
        size_t got = fread(input_buf.data() + len, 1, input_buf.size() - len, stdin);
        if (got == 0) break;
        len += got;
    }
    input_buf.resize(len + 1);
    input_buf[len] = '\0';  // 哨兵，保证解析最后一个数时读不到越界字符
    input_pos = 0;
}

// 跳过空白等分隔符并吃掉负号，返回这个数是否为负
bool read_sign() {
    while (input_buf[input_pos] != '-' && (input_buf[input_pos] < '0' || input_buf[input_pos] > '9')) {
        input_pos++;
    }
    if (input_buf[input_pos] == '-') {
        input_pos++;
        return true;
    }
    return false;
}

ll read_long() {
    bool negative = read_sign();
    ll value = 0;
    while (input_buf[input_pos] >= '0' && input_buf[input_pos] <= '9') {
        value = value * 10 + (input_buf[input_pos] - '0');
        input_pos++;
    }
    return negative ? -value : value;
}

int read_small() {
    bool negative = read_sign();
    int value = 0;
    while (input_buf[input_pos] >= '0' && input_buf[input_pos] <= '9') {
        value = value * 10 + (input_buf[input_pos] - '0');
        input_pos++;
    }
    return negative ? -value : value;
}

// 在 x[1..n] 中找第一个 >= value 的下标；找不到返回 n + 1
int first_not_less(ll value) {
    int left = 1, right = n + 1;  // 答案区间是半开区间 [1, n+1]
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (x[mid] >= value) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// 在 x[1..n] 中找最后一个 <= value 的下标；找不到返回 0
int last_not_greater(ll value) {
    int left = 0, right = n;  // 答案区间是半开区间 [0, n]
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (x[mid] <= value) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

// 读入炸弹坐标与半径，并二分出每个炸弹「直接引爆」的下标区间
void read_input() {
    load_input();
    n = read_small();
    for (int i = 1; i <= n; i++) {
        x[i] = read_long();
        r[i] = read_long();
    }
    for (int i = 1; i <= n; i++) {
        lo[i] = first_not_less(x[i] - r[i]);
        hi[i] = last_not_greater(x[i] + r[i]);
    }
    input_buf.clear();
    input_buf.shrink_to_fit();  // 后面的图结构要占几十 MB，先把输入缓冲还回去
}

// 追加一条出边（CSR 靠 push_back 顺序填充，adj_start 记录每条边段的起点）
void add_edge(int v) {
    adj_to.push_back(v);
    edge_cnt++;
}

// 建图：
//   1. 线段树的内部节点 u 向左右儿子连边，使「走到这个节点」等于「走到它覆盖的全部叶子」；
//   2. 炸弹叶子向「它直接引爆的下标区间」在线段树上的 O(log n) 个规范节点连边。
// 节点按编号升序处理，正好是「先内部节点、后叶子（即炸弹顺序）」，所以一趟就能填好 CSR。
void build_graph() {
    m = 1;
    while (m < n) m <<= 1;
    node_cnt = m + n - 1;

    adj_start.assign(node_cnt + 2, 0);
    adj_to.clear();
    adj_to.reserve(2 * (m - 1) + 20 * n + 8);
    edge_cnt = 0;

    for (int u = 1; u <= node_cnt; u++) {
        adj_start[u] = edge_cnt;
        if (u < m) {
            // 线段树内部节点：连向左右儿子，编号超过实际叶子范围的儿子不存在
            for (int child = 2 * u; child <= 2 * u + 1; child++) {
                if (child <= node_cnt) add_edge(child);
            }
        } else {
            // 叶子 u 就是炸弹 i，向 [lo[i], hi[i]] 的规范分解节点连边
            int i = u - m + 1;
            int left = m + lo[i] - 1;
            int right = m + hi[i] - 1;
            while (left <= right) {
                if (left & 1) add_edge(left++);
                if (!(right & 1)) add_edge(right--);
                left >>= 1;
                right >>= 1;
            }
        }
    }
    adj_start[node_cnt + 1] = edge_cnt;
}

int dfn[MAXM + MAXN];        // dfn[u]：Tarjan 时间戳，0 表示还没访问
int low[MAXM + MAXN];        // low[u]：u 及其 DFS 子树能回溯到的最小 dfn
int scc[MAXM + MAXN];        // scc[u]：u 所属强连通分量编号（从 1 开始）
char in_stack[MAXM + MAXN];  // u 是否还在顶点栈上，只有 0/1，用 char 省 3MB 内存
int dfs_clock;
int scc_cnt;

int vstack[MAXM + MAXN];  // Tarjan 的顶点栈
int vstack_top;

// 每次弹出一个 SCC，就把它的成员按顺序写进 pop_order，
// 于是编号 id 的成员正好是 pop_order[scc_begin[id] .. scc_begin[id+1])。
int pop_order[MAXM + MAXN];
int scc_begin[MAXM + MAXN];
int pop_cnt;

struct Frame {
    int u;    // 这一层正在处理的节点
    int idx;  // 这一层枚举到哪条出边
};
Frame frames[MAXM + MAXN];  // 手写的调用栈，替代递归（原因见文件头）

// 迭代版 Tarjan。SCC 编号按「汇点先被弹出」的顺序递增，
// 因此任意边 A -> B 都满足 scc[A] > scc[B]，编号递增本身就是拓扑序。
void tarjan() {
    for (int root = 1; root <= node_cnt; root++) {
        if (dfn[root] != 0) continue;
        int top = 1;
        frames[1].u = root;
        frames[1].idx = adj_start[root];
        dfn[root] = low[root] = ++dfs_clock;
        vstack[++vstack_top] = root;
        in_stack[root] = 1;

        while (top > 0) {
            int u = frames[top].u;
            int idx = frames[top].idx;
            if (idx < adj_start[u + 1]) {
                int v = adj_to[idx];
                frames[top].idx = idx + 1;
                if (dfn[v] == 0) {
                    // 树边：进入 v
                    dfn[v] = low[v] = ++dfs_clock;
                    vstack[++vstack_top] = v;
                    in_stack[v] = 1;
                    top++;
                    frames[top].u = v;
                    frames[top].idx = adj_start[v];
                } else if (in_stack[v] && dfn[v] < low[u]) {
                    // 只有还留在栈上的点才能更新 low
                    low[u] = dfn[v];
                }
                continue;
            }

            // u 的所有出边都走完了，回溯，把 low 传给父节点
            top--;
            if (top > 0) {
                int parent = frames[top].u;
                if (low[u] < low[parent]) low[parent] = low[u];
            }
            if (low[u] == dfn[u]) {
                // u 是本 SCC 在 DFS 树上的最高点，弹出整块
                scc_cnt++;
                while (true) {
                    int w = vstack[vstack_top--];
                    in_stack[w] = 0;
                    scc[w] = scc_cnt;
                    pop_order[pop_cnt++] = w;
                    if (w == u) break;
                }
                scc_begin[scc_cnt + 1] = pop_cnt;
            }
        }
    }
}

// 缩点后按拓扑序（SCC 编号递增）传播每个 SCC 能引爆的炸弹区间。
// 「能引爆的炸弹」一定是连续一段，所以只需维护区间左右端点：
// 用 min/max 合并，重复到达同一个炸弹也不会算重。
void propagate() {
    // SCC_MIN 初值取 +inf、SCC_MAX 初值取 0，只含线段树节点的 SCC 会被算成空区间
    vector<int> scc_min(scc_cnt + 2, INT_MAX);
    vector<int> scc_max(scc_cnt + 2, 0);
    for (int i = 1; i <= n; i++) {
        int id = scc[leaf_of(i)];
        if (i < scc_min[id]) scc_min[id] = i;
        if (i > scc_max[id]) scc_max[id] = i;
    }

    for (int id = 1; id <= scc_cnt; id++) {
        for (int p = scc_begin[id]; p < scc_begin[id + 1]; p++) {
            int u = pop_order[p];
            for (int e = adj_start[u]; e < adj_start[u + 1]; e++) {
                int v = adj_to[e];
                int j = scc[v];
                if (j == id) continue;  // SCC 内部的边不带来新信息
                if (scc_min[j] < scc_min[id]) scc_min[id] = scc_min[j];
                if (scc_max[j] > scc_max[id]) scc_max[id] = scc_max[j];
            }
        }
    }

    ll answer = 0;
    for (int i = 1; i <= n; i++) {
        int id = scc[leaf_of(i)];
        ll weight = i;                             // 第 i 个炸弹的权值，顺手提升成 ll
        ll reachable = scc_max[id] - scc_min[id] + 1;  // 第 i 个炸弹能引爆的个数
        answer = (answer + weight * reachable) % MOD;
    }
    printf("%lld\n", answer);
}

int main() {
    read_input();
    build_graph();
    tarjan();
    propagate();
    return 0;
}

复杂度

设 $n$ 为炸弹数， $m = 2^{\lceil \log_2 n\rceil}$ ，图中节点数 $V = m + n - 1$ ，边数 $E = O(n\log n)$ 。

步骤	时间	空间
二分求 $[lo_i, hi_i]$	$O(n\log n)$	$O(n)$
建线段树优化图	$O(V + E)$	$O(V + E)$
迭代 Tarjan 求 SCC	$O(V + E)$	$O(V)$
DAG 上传播区间端点	$O(V + E)$	$O(V)$
统计答案	$O(n)$	—
合计	$O(n\log n)$	$O(n\log n)$

代入上限 $n = 5\times10^5$ ： $m = 2^{19} = 524288$ ， $V = 1024287$ 。每个炸弹的规范分解节点数平均约 16、最多 24；把 $n$ 个炸弹的区间都取成「节点数最多」的那一组时炸弹边共 $9\,498\,903$ 条，真实数据受 $r_i$ 约束，实测最大 $8\,436\,224$ 条（含线段树自身 $1048574$ 条）。八组 $n=5\times10^5$ 的极端数据实测：最慢 680 ms、峰值内存 73 MiB，均在 1000 ms / 250 MiB 内。

解法二：不建图的双向扫描

思路

解法一花了 $O(n\log n)$ 的力气去精确表示「 $i$ 能到谁」。但本题最终只要个数，而个数由一个更弱的结构决定：能引爆的炸弹构成一段连续下标区间。既然如此，只要能为每个 $i$ 求出这段区间的左右端点 $[L_i, R_i]$ ，答案就是 $R_i - L_i + 1$ ，整张图都是多余的。

剩下唯一的问题就是：怎么不建图地求出所有 $[L_i, R_i]$ 。

一个必须想清楚的陷阱

最自然的贪心是「左右分别扫一遍」：从左往右只做向左的合并，求出左端点；再从右往左只做向右的合并，求出右端点。但这样是错的，因为左右会互相喂：某个炸弹可能先被右边一个超大炸弹拽过去，从而获得更远的左端点；这个左端点又可能让它够到更左的炸弹，那个炸弹的右向射程又更大……

所以真正的难点不是「怎么扫」，而是「扫几遍才够」。解法二的全部技巧就是证明两遍就够。

记号

对每个炸弹 $i$ 维护三个量：闭包块的左端点 $L_i$ 、右端点 $R_i$ 、以及右向射程 $c_i$ 。 $c_i$ 的含义是：这个块从 $x_i$ 出发往右最远能打到 $x_i + c_i$ 。注意 $c_i$ 记的是相对 $x_i$ 的差值，不是绝对坐标，这样两块合并时直接相减即可。

初值 $L_i = R_i = i$ ， $c_i = r_i$ 。

第一遍：从左往右，只往左合并

$i$ 从 $2$ 枚举到 $n$ 。每次看当前块左边紧邻的炸弹 $p = L_i - 1$ ：

如果块里没有任何东西能打到 $x_p$ ，即 $x_i - x_p > c_i$ ，停止；
否则把 $p$ 所在的那一整块并进来： $L_i \leftarrow L_p$ ，并把它带来的右向射程折算到 $x_i$ 的坐标上， $c_i \leftarrow \max(c_i,\; c_p - (x_i - x_p))$ 。

这里有个容易写错的地方：并进来的不是单个 $p$ ，而是整个块 $[L_p, p]$ ，因为那一段本来就已互相引爆， $p$ 一响它们全响。所以合并后左端点直接跳到 $L_p$ ，一步顶很多步。

代码里被并进来的 $p$ 永远等于 $L_i - 1$ ，且 $L_i$ 单调左移，这保证了不会来回震荡。

第一遍结束后，对每个 $i$ 我们得到了一个块的左端点（记作 $\bar L_i$ ）和一个右向射程 $\bar c_i$ 。有人会觉得「既然只往左合并过，那 $\bar c_i$ 是不是没用、要重算」——恰恰相反，下面第二遍就靠着它。

第二遍：从右往左，靠旧射程往右吸收

$i$ 从 $n-1$ 倒着枚举到 $1$ 。每次看当前块右边紧邻的块，其左端点 $q = R_i + 1$ ：

如果 $\bar c_i$ 够不到 $x_q$ ，即 $x_q - x_i > \bar c_i$ ，停止；
否则把整块 $[q, R_q]$ 并入： $L_i \leftarrow \min(L_i, L_q)$ ， $R_i \leftarrow R_q$ 。

关键点是：这一遍判据里用的始终是第一遍留下的 $\bar c_i$ ，全程不更新。 为什么不需要更新？因为要越过当前块的右端继续往右推进，只能用「初始块 $[\bar L_i, i]$ 里的炸弹」的射程；而这个初始块的右向射程上界已经被第一遍完整地汇总成 $\bar c_i$ 了。后来并进来的那些块，它们的右向能力再强也只能把右端推到它们自己闭包能达到的位置，也就是 $R_q$ ，已经通过 $R_i \leftarrow R_q$ 体现，不需要折回 $c_i$ 再算一次。

这样两遍下来， $L_i$ 既包含了第一遍向左闭包的结果，又吸收了第二遍从右侧大炸弹传回来的更左端点； $R_i$ 是原样接上去的右端。

为什么两遍就够了：正确性证明

“引爆集合是连续区间”沿用解法一第四步的结论。下面把第一遍的结果记作 $\bar L_i$ 与 $\bar c_i$ 。

引理 1（第一遍算的是什么）：第一遍结束后，块 $[\bar L_i, i]$ 恰是「只用下标 $\leqslant i$ 的炸弹」对 $i$ 做左向闭包的结果，且

\bar c_i = \max_{b \in [\bar L_i,\, i]} (x_b + r_b) - x_i .

归纳证明：处理 $i$ 时 $1 \ldots i-1$ 都已结算完毕。循环每次取 $p = \bar L_i - 1$ ，把已算好的块 $[\bar L_p, p]$ 整体并入并同步取射程上界，于是 $(\bar L_i, \bar c_i)$ 逐步变成「 $i$ 与左边一段已闭包的块合并后的结果」。循环退出时 $x_i - x_{\bar L_i - 1} > \bar c_i$ ，即前一个块无法被够到，前缀闭包收缩完毕，等式自然成立。

这一步同时给出了一个有用的副产品：并入的是整块而不是单个点，因为块内早已互相引爆；因此左端点一步跳到 $\bar L_p$ ，而不是 $p-1$ 。

引理 2（第二遍的判据是充要的）：设此刻算法块为 $[L_i, R_i]$ 且 $R_i < n$ ，则真实闭包能越过 $R_i$ 当且仅当 $x_{R_i+1} \leqslant x_i + \bar c_i$ 。

充分性： $\bar c_i$ 是初始块 $[\bar L_i, i]$ 的右向能力上界（引理 1），而初始块内的炸弹都是真可达的，所以只要够得到， $R_i+1$ 就真的会被引爆。
必要性：第二遍倒序枚举，所以此刻用到的 $R_q$ 已经是 $q$ 的最终右端（归纳假设）。既然 $R_q$ 是闭包右端，块 $[L_q, R_q]$ 里任何炸弹都不可能炸到 $R_q$ 右边；而这些块正是第二遍已并入的部分（都已包在初始闭包内）。所以若还能越过 $R_i$ ，推动者必在初始块 $[\bar L_i, i]$ 里，其右向能力不超过 $x_i + \bar c_i$ 。

定理：两遍结束后 $[L_i, R_i]$ 就是真实的 $[L_i^*, R_i^*]$ 。

$R_i = R_i^*$ ：由引理 2 的充要性，循环判据与「真闭包能否右扩」完全等价；循环一直推进到 $R_i = n$ 或判据失效，而失效正意味着真闭包也到底了。
$L_i = L_i^*$ ：第一遍给出左向部分；第二遍每并入一块就取 $L_i \leftarrow \min(L_i, L_q)$ ，把右侧大炸弹传回来的更左端点也吸收进来。最终块同时满足 $\min_{b \in [L_i,R_i]} lo_b = L_i$ 与 $\max_{b \in [L_i,R_i]} hi_b = R_i$ （双向闭），即闭包不动点；而所有被并进来的块都由初始可达关系驱动，故块不会超出真闭包。两者夹出 $[L_i, R_i] = [L_i^*, R_i^*]$ 。

一句话概括：第一遍负责「左端点」，第二遍负责「右端点」，两遍之间的桥就是那个故意不更新的 $\bar c_i$ 。 它之所以能一直用，是因为越过右端的外推只能由初始块驱动，而初始块的右向能力已被引理 1 固化成 $\bar c_i$ 。

上述三条引理与两向闭合性质，除归纳证明外还做了机器核查： $n \leqslant 7$ 、坐标与半径全组合（坐标上限 8、半径上限 4，共 $2\,812\,500$ 组）以及 $1.5\times10^5$ 组随机数据上， $\bar c_i = \max(x_b+r_b)-x_i$ 、双向闭合、以及块不超出真闭包三项全部无例外。

为什么是 $O(n)$ ：摊还分析

这是本题最容易糊弄过去的一步，必须算清楚。

第一遍：每次合并让 $L_i$ 跳到 $L_p \leqslant p = L_i - 1$ ，左端点严格变小。只靠这一点只能得到「单个 $i$ 至多 $i-1$ 次」，加总是 $O(n^2)$ ，不够。

正确的账要记在「被吸收的下标」上。把一次合并记作消耗了下标 $h = L_i - 1$ ；由于并入的是整块 $[L_h, h]$ ，合并后 $L_i = L_h \leqslant h$ 。

关键观察： $h$ 在同一遍里至多被消耗一次。理由：消耗 $h$ 的那次合并会把 $L_i$ 直接赋成 $L_h$ ，而 $L_h \leqslant h$ ，所以 $h$ 一旦被消耗，消耗者自己的左端点已落到 $h$ 或更左；此后任何新炸弹 $i' > i$ 的 $L_{i'}$ 只会单调不增，且每次下降都是直接跳到某个块的左端点，因此不会再出现 $L_{i'} = h+1$ 这种「恰好差一格」的状态，而只有 $L_{i'} = h+1$ 才能消耗 $h$ 。

关于这一处的严格性：上面「不会再停在 $h+1$ 」一句依赖的是「 $L$ 单调不增 + 每次合并跳到一个块的左端点」这两个事实的直观推论，本文没有把它写成完整的形式化归纳证明。该结论已用穷举（ $n \leqslant 7$ 全组合）与爬山搜索（ $n \leqslant 150$ ，每组 2 万步）逐下标统计消耗次数、最大值恒为 1 做过验证，但读者若要引用，宜视为「有强证据支持的断言」而非已完成的严格证明。

内层每执行一次恰好消耗一个此前未消耗的 $h \in [1, n-1]$ ，故第一遍内层总次数 $\leqslant n-1$ 。

第二遍：完全对称。每次吸收让 $R_i$ 跳到 $R_q \geqslant q = R_i + 1$ ，严格变大；同理一个下标在同一遍里至多被消耗一次，内层总次数 $\leqslant n-1$ 。

两遍相加 $\leqslant 2n-2$ ，外层各 $O(n)$ ，故整体 $O(n)$ 。

这个界是紧的： $n \leqslant 7$ 的完全穷举中第一遍内层总是 $\leqslant n-1$ 且能取到 $n-1$ （最优实例取 $n-1$ ）； $n = 3\times10^5$ 量级的随机数据上逐个下标统计消耗次数，最大值恒为 1； $n = 5\times10^5$ 的极端数据上两遍内层总数实测正好是 $2n-2 = 999\,998$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 16:31
 * update_at: 2026-10-23 16:53
 */
// alt1.cpp：不建图的双向扫描，O(n) 时间 / O(n) 空间。
//
// 主解用线段树优化建图 + Tarjan 缩点把「点向区间连边」压到 O(n log n)；
// 本解完全不走图论：直接利用「引爆集合必为连续下标区间」这一性质，
// 对每个炸弹维护它最终能引爆的区间端点，先做一遍只向左的闭包，再做一遍向右的吸收。
// 关键在于向左闭包时空闲出来的「右向射程」在第二趟依然有效（不是漏更新），
// 以及两趟的内层 while 总次数都不超过 n-1，因此整体线性。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 500005;  // 炸弹个数上限
const ll MOD = 1000000007;

int n;                // 炸弹个数
ll x[MAXN];           // x[i]：第 i 个炸弹的坐标（严格递增）
ll r[MAXN];           // r[i]：第 i 个炸弹的爆炸半径
int left_end[MAXN];   // left_end[i]：当前 i 所在闭包块的左端点
int right_end[MAXN];  // right_end[i]：当前 i 所在闭包块的右端点
ll reach[MAXN];       // reach[i]：该块从 x[i] 往右最远能炸到 x[i] + reach[i]

// 输入最多 1e6 个 64 位整数（坐标、半径都可到 10^18 量级，约 20MB 文本），
// 用 fread 整块读入再手工解析，避免 iostream / scanf 在大输入上耗时过多。
// 缓冲区按实际长度动态增长，不能写死大小，否则大输入会被截断成错答案。
vector<char> inbuf;
size_t inlen = 0;
size_t inpos = 0;

void load_all() {
    inbuf.resize(1 << 20);
    inlen = 0;
    while (true) {
        if (inlen == inbuf.size()) inbuf.resize(inbuf.size() * 2);
        size_t got = fread(inbuf.data() + inlen, 1, inbuf.size() - inlen, stdin);
        if (got == 0) break;
        inlen += got;
    }
}

// 读下一个整数（可能带负号）；读到末尾之后一律返回 0
ll read_int() {
    while (inpos < inlen && (inbuf[inpos] < '0' || inbuf[inpos] > '9') && inbuf[inpos] != '-') {
        inpos++;
    }
    bool negative = false;
    if (inpos < inlen && inbuf[inpos] == '-') {
        negative = true;
        inpos++;
    }
    ll value = 0;
    while (inpos < inlen && inbuf[inpos] >= '0' && inbuf[inpos] <= '9') {
        value = value * 10 + (inbuf[inpos] - '0');
        inpos++;
    }
    return negative ? -value : value;
}

void read_input() {
    load_all();
    n = int(read_int());
    for (int i = 1; i <= n; i++) {
        x[i] = read_int();
        r[i] = read_int();
        left_end[i] = i;
        right_end[i] = i;
        reach[i] = r[i];
    }
}

// 第一趟：i 从小到大，只往左扩展。
// 队列尾指针 left_end[i] 每跳一次就变成 left_end[left_end[i] - 1]，
// 也就是把左边那一整块闭包合并进来；合并时同步取两块的右向射程较大者。
// 因为 x 严格递增且左块在 i 左边，新的右向射程写成
// 「左块射程 - 两点距离」，再与自己的射程取 max。
void sweep_left() {
    for (int i = 2; i <= n; i++) {
        while (left_end[i] > 1 && x[i] - x[left_end[i] - 1] <= reach[i]) {
            int prev = left_end[i] - 1;
            ll spread = reach[prev] - (x[i] - x[prev]);
            if (spread > reach[i]) reach[i] = spread;
            left_end[i] = left_end[prev];
        }
    }
}

// 第二趟：i 从大到小，只往右吸收。
// 判断标准仍然是第一趟留下的 reach[i]（这里刻意不更新，理由见正文）：
// 越过当前块右端之后还能继续够到的东西，只可能由初始块 [left_end[i], i] 里的炸弹直接炸到，
// 而初始块的右向射程已经固化成 reach[i]。
// 吸收进来的是 right_end[i] + 1 那一整块的最终答案区间，所以左端点取 min、右端点直接接上。
void sweep_right() {
    for (int i = n - 1; i >= 1; i--) {
        while (right_end[i] < n && x[right_end[i] + 1] - x[i] <= reach[i]) {
            int next = right_end[i] + 1;
            if (left_end[next] < left_end[i]) left_end[i] = left_end[next];
            right_end[i] = right_end[next];
        }
    }
}

int main() {
    read_input();
    sweep_left();
    sweep_right();

    ll answer = 0;
    for (int i = 1; i <= n; i++) {
        ll count = right_end[i] - left_end[i] + 1;
        answer = (answer + (ll)i % MOD * (count % MOD)) % MOD;
    }
    printf("%lld\n", answer);
    return 0;
}

复杂度

步骤	时间	空间
读入	$O(n)$	$O(n)$
第一遍向左闭包	$O(n)$ （内层 $\leqslant n-1$ 次）	—
第二遍向右吸收	$O(n)$ （内层 $\leqslant n-1$ 次）	—
统计答案	$O(n)$	—
合计	$O(n)$	$O(n)$

空间只有几个长度 $n$ 的数组（left_end、right_end、reach 与坐标半径），加读入缓冲，约 $32$ MiB。同一批八组 $n=5\times10^5$ 极端数据实测最慢 51 ms。

复杂度对比

	解法一	解法二
时间	$O(n\log n)$	$O(n)$
空间	$O(n\log n)$ （约 73 MiB）	$O(n)$ （约 32 MiB）
实测最慢（ $n=5\times10^5$ ，同一批 8 组数据）	680 ms	51 ms
是否需要建图	需要， $10^6$ 点 / $10^7$ 边	不需要
关键难点	区间连边的线段树分解、迭代 Tarjan、 $\min/\max$ 合并	证明「两遍就够」与摊还 $O(n)$ 界
可迁移性	高，「点向区间连边」是通用套路	中，依赖「引爆集合是区间」这一维结构

选择建议：要通过本题且代码短，用解法二；要学习可迁移的图论建模技巧，用解法一。两者答案必然一致，已用大规模对拍交叉验证（见下方验证说明）。

总结

本题的两条解法链，恰好代表了两类完全不同的思路：

解法一：老老实实建图，再想办法把图变小。

重构图的表示：引爆关系是「点 → 一段下标连续区间」，用「内部节点连儿子 + 叶子向 $O(\log n)$ 个规范节点连边」把边数从 $O(n^2)$ 压到 $O(n\log n)$ 。这是线段树优化建图的标准套路。
发现集合的结构：能引爆的炸弹集合是连续区间，于是「可达集合」这个对象只需两个端点就能刻画。
选对合并方式：DAG 上按点权求和统计可达点数会重复计数（这是本题最经典的错误做法），而按区间端点做 $\min/\max$ 合并则天然免疫重复。

三条缺一不可：只做第 1 条会 WA，只做第 2 条仍会因边数过多而 TLE/MLE。

解法二：干脆不建图，直接在区间上做闭包。

它把「图可达性」整个扔掉，只保留「集合是区间」这一条性质，于是每个炸弹的状态从「一个可达点集」退化成「三个数」。代价是要多做一个证明：既要说明两遍扫描为什么覆盖了「先右再左再右」这类来回喂的情形，也要说明内层 $while$ 为什么不会退化。本题最值得记住的两点，正是这两个证明所对应的两个观察——右向射程在向左闭包时不会失效，以及一个下标在一遍里至多被吸收一次。

实现上还有两个容易被忽视的点：解法一的图有 $10^7$ 量级的边，用 CSR 比链式前向星省一半内存；图里存在 $7.5\times10^5$ 层深的链，递归 Tarjan 需要 60MiB 栈，必须改成显式栈迭代。解法二的输入文本最大约 20 MiB，读入缓冲必须按实际长度增长，写死 4 MiB 会静默截断输入、算出完全错误的答案。

参考与致谢

解法二（不建图的双向扫描）的基本思路来自下列公开题解，本文在阅读后重写了叙述与代码：

Krystallos（uid 124683），《题解 P5025【[SNOI2017]炸弹】》，https://www.luogu.com.cn/article/55ow5kwh。该文提出用「先向右扫一遍求左端点、再从右向左扫一遍求右端点」的线性做法，并声称总复杂度为 $O(n)$ 。

本文补充的内容

为避免混淆原创归属，这里明确区分来源：

内容	来源
用两遍扫描代替建图、以及用相对差值记录右向射程的基本设计	原题解
引理 1（第一遍结束时 $\bar c_i = \max_{b\in[\bar L_i,i]}(x_b+r_b)-x_i$ ，即射程上界是精确的）	本文重新论证
引理 2（第二遍的判据与「真闭包能否右扩」充要，因而不需更新射程）	本文重新论证
两遍后块双向闭合即为闭包不动点、且不超出真闭包的收敛性论证	本文补充
摊还分析：每个下标在一遍内至多被消耗一次，故每遍 $\leqslant n-1$ 、总计 $\leqslant 2n-2$	本文重新论证
上界的紧性证据（实测内层总数恰好取到 $2n-2$ ）	本文实测
`alt1.cpp` 全部代码	本文独立实现

原题解对上述两点（为何第二遍不必更新射程、以及为何两遍的内层循环总次数是线性而非平方）只给了一段定性说明，未构成证明；本文的引理与摊还界均为独立推导，本文的摊还部分还明确标注了其中一处仅依赖直观论证、未完成形式化。

已核查但未采纳的题解

DengDuck（uid 501947），《P5025 [SNOI2017] 炸弹邪修做法》，https://www.luogu.com.cn/article/uhk0n2gm。该文用单调栈配合固定 64 轮外部迭代。本文核查后确认其结果正确，但未采纳，原因有两点：其一，它经实测只需 1 轮即达正确结果（200 000 组随机数据上第 2 轮从未改变任何状态），后 63 轮为冗余空转，按「每下标每遍至多消耗一次」实为同一类闭包扫描，不构成独立解法；其二，其固定 64 轮导致 $n=5\times10^5$ 时耗时 $O(64n)$ ，本机实测约 1.2–1.5 s，超过本题 1 s 时限。

以下题解与解法一同属「线段树优化建图 + Tarjan 缩点」路线，只作交叉参考，未引入新思路：

NaCly_Fish（uid 115864），《[SNOI2017]炸弹：线段树优化建图》，https://www.luogu.com.cn/article/c1q29bjd
subarude（uid 162865），《P5025 【[SNOI2017]炸弹】》，https://www.luogu.com.cn/article/62tq0m7k
小蒟蒻皮皮鱼（uid 177510），《题解 P5025 【[SNOI2017]炸弹】》，https://www.luogu.com.cn/article/swjui3xu

目录