题解：炸弹连锁引爆计数

问题转化

每个炸弹 $i$ 可以引爆坐标在 $[X_i - R_i, X_i + R_i]$ 内的所有炸弹。
初始引爆 $i$ 后，所有被直接或间接引爆的炸弹都会爆炸，要求对每个 $i$ 求出引爆的炸弹总数，然后计算：

$$\sum_{i=1}^N (i \times \text{cnt}_i) \bmod (10^9+7) $$

其中 $\text{cnt}_i$ 是炸弹 $i$ 能引爆的总炸弹数。

关键观察

1. 引爆的传递性

如果炸弹 $i$ 能引爆 $j$，$j$ 能引爆 $k$，那么 $i$ 也能引爆 $k$。
因此，引爆关系构成一个有向图（$i$ 向所有在 $[X_i - R_i, X_i + R_i]$ 内的 $j$ 连边），需要求每个点能到达的点数。

2. 区间合并

由于坐标递增，引爆区间 $[L_i, R_i] = [X_i - R_i, X_i + R_i]$ 可能不是单调的，但传递引爆相当于：

• 从 $i$ 出发，能引爆的炸弹形成一个连续区间 $[left_i, right_i]$（按坐标排序后的编号区间）。
• 证明：若 $i$ 能引爆 $j$ 和 $k$（$j < k$），且坐标在 $j$ 和 $k$ 之间的炸弹 $t$ 必然在 $[X_j - R_j, X_k + R_k]$ 的覆盖范围内，通过连锁反应也会被引爆。

因此问题变为：对每个 $i$，求最小的 $l$ 和最大的 $r$，使得从 $i$ 出发能覆盖到 $l$ 到 $r$ 的所有炸弹。

3. 递推关系

设 $left_i$ 为从 $i$ 出发能引爆的最左边炸弹编号，$right_i$ 为最右边编号。
初始：$left_i = \min\{j \mid X_j \ge X_i - R_i\}$，$right_i = \max\{j \mid X_j \le X_i + R_i\}$。

但实际引爆还会扩展：
如果 $i$ 能引爆 $j$，那么 $i$ 的引爆区间会扩展到 $[left_j, right_j]$。
因此需要迭代扩展：

$$left_i = \min_{j \in [left_i, right_i]} left_j$$ $$right_i = \max_{j \in [left_i, right_i]} right_j$$

4. 优化扩展过程

这是一个区间最值扩展问题，可以用单调栈+倍增优化。

定义：

• $L[i][k]$：从 $i$ 出发，扩展 $2^k$ 步后能到达的最左编号
• $R[i][k]$：从 $i$ 出发，扩展 $2^k$ 步后能到达的最右编号

初始：

L[i][0] = \text{lower_bound}(X_i - R_i) R[i][0] = \text{upper_bound}(X_i + R_i) - 1

递推：

$$L[i][k] = \min_{j \in [L[i][k-1], R[i][k-1]]} L[j][k-1] $$$$R[i][k] = \max_{j \in [L[i][k-1], R[i][k-1]]} R[j][k-1] $$

5. 快速求区间最值

由于 $N$ 可达 $5\times 10^5$，需要 $O(\log N)$ 查询区间最值。
用 ST 表预处理 $L$ 和 $R$ 的区间最小值/最大值。

设 $minST[l][r]$ 为 $L[i][0]$ 在区间 $[l, r]$ 的最小值，$maxST[l][r]$ 类似。

那么：

$$L[i][k] = \min_{j \in [L[i][k-1], R[i][k-1]]} L[j][k-1] $$

可以用 ST 表 $O(1)$ 查询。

6. 算法步骤

1. 读入 $N$ 和 $(X_i, R_i)$，坐标严格递增。
2. 预处理 ST 表，用于查询任意区间 $[l, r]$ 的 $L[i][0]$ 最小值和 $R[i][0]$ 最大值。
3. 初始化 $L[i][0]$ 和 $R[i][0]$：
   • $L[i][0] =$ 最小的 $j$ 满足 $X_j \ge X_i - R_i$（二分查找）
   • $R[i][0] =$ 最大的 $j$ 满足 $X_j \le X_i + R_i$（二分查找）
4. 倍增迭代 $K = \lceil \log_2 N \rceil$ 次：
   • 对于 $k = 1$ 到 $K$：
     • 对于每个 $i$，用 ST 表查询 $[L[i][k-1], R[i][k-1]]$ 的 $L$ 最小值作为 $L[i][k]$
     • 用 ST 表查询 $[L[i][k-1], R[i][k-1]]$ 的 $R$ 最大值作为 $R[i][k]$
5. 计算最终 $left_i$ 和 $right_i$：
   • 初始 $l = i$，$r = i$
   • 从 $k = K$ 向下到 $0$：
     • 用 $l$ 和 $r$ 查询区间 $[l, r]$ 的 $L$ 最小值 $l'$ 和 $R$ 最大值 $r'$
     • 如果 $l' < l$ 或 $r' > r$，则更新 $l = l'$，$r = r'$，并继续
6. 最终引爆数 $cnt_i = r - l + 1$
7. 计算答案：$$\text{ans} = \sum_{i=1}^N (i \times cnt_i) \bmod (10^9+7) $$

7. 复杂度分析

• 预处理 ST 表：$O(N \log N)$
• 二分查找初始区间：$O(N \log N)$
• 倍增迭代：$O(N \log N)$
• 总复杂度：$O(N \log N)$
• 空间复杂度：$O(N \log N)$

8. 注意事项

• 坐标和半径很大，用 long long 存储
• ST 表查询区间最值时注意边界
• 最终答案取模 $10^9+7$