仓库源文，站点原文

title: "题解 - [Luogu P5025] [LOJ 2255] [SNOI2017] 炸弹" categories:

题面

1000 ms / 125.00 MB

在一条直线上有 $n$ 个炸弹, 每个炸弹的坐标是 $x_i$, 爆炸半径是 $r_i$, 当一个炸弹爆炸时, 如果另一个炸弹所在位置 $x_j$ 满足: $|x_j-x_i| \le r_i$, 那么, 该炸弹也会被引爆.

现在, 请你帮忙计算一下, 先把第 $i$ 个炸弹引爆, 将引爆多少个炸弹呢?

答案对 $10^9 + 7$ 取模

第一行, 一个数字 $n$, 表示炸弹个数第 $2 \sim n+1$ 行, 每行两个整数, 表示 $x_i$, $r_i$, 保证 $x_i$ 严格递增

一个数字, 表示 $\sum \limits_{i=1}^n i\times$ 炸弹 $i$ 能引爆的炸弹个数

【数据范围】

对于 $20\%$ 的数据: $n\leq 100$

对于 $50\%$ 的数据: $n\leq 1000$

对于 $80\%$ 的数据: $n\leq 100000$

对于 $100\%$ 的数据: $1\le n\leq 500000$, $-10^{18}\leq x{i}\leq 10^{18}$, $0\leq r{i}\leq 2\times 10^{18}$

线段树优化建图然后 Tarjan 跑强连通分量的做法比较显然, 这里介绍一个基于单调栈维护边界的线性做法

首先我们假设炸弹只能引爆左边的炸弹, 此时可以很容易地按顺序求出左边界 l[i]

之后我们把右边的炸弹纳入考虑中, 右边界 r[i] 可以按左边界一样的方法逆序得出

注意考虑右边界后, 左边界会变动 (即右边炸弹的引爆范围覆盖的当前炸弹的左边界)

$O(n)$

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:Luogu_P5025 Luogu/P5025/0.cpp %} </details>