#5758. 「ROI 2026 Day2」夜，街，灯，药店

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day2 T2. Ночь, улица, фонарь, аптека

在一条长街上排列着一些灯柱，共有 $n$ 盏灯安装在这些灯柱上。我们沿着街道建立坐标系。第 $i$ 盏灯所在的灯柱位于坐标 $x_i$ 处。在本题的前六个子任务（分值为 $85$ 分）中，任何两盏灯都不会安装在同一个灯柱上，即所有的 $x_i$ 都是互不相同的。在最后两个子任务中，每个灯柱上最多可以安装两盏灯。

为了照明街道，可以开启其中的一部分灯。开启的第 $i$ 盏灯具有亮度 $s_i$。它从所属的灯柱开始，可以照亮街道上一段长度为 $s_i$ 米的连续区域。每盏开启的灯既可以向左转向，也可以向右转向。如果将第 $i$ 盏灯向左转向，它将照亮街道区间 $[x_i - s_i, x_i]$；如果向右转向，则照亮区间 $[x_i, x_i + s_i]$。

我们选择一个非空的灯泡子集用于街道照明。如果能为选中的每盏灯确定向左或向右的朝向，并满足以下两个条件，则称该灯泡集合是经济型的：

• 所有照亮区域合并后形成街道上的一段连续区间；
• 没有任何长度大于零的路段被两盏或更多的灯同时照亮。

下图展示了题目中第二个样例中包含两盏灯的经济型子集，以及照亮连续路段的方式。每个灯泡上方标有其亮度。

请计算经济型灯泡子集的数量。输出结果对 $10^9+7$ 取模后的余数。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示灯的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $s_i$ $(1 \leq x_i \le 5\cdot 10^5, 1 \le s_i \leq 5 \cdot 10^5, x_1 \le x_2 \le \ldots \le x_n)$，分别表示第 $i$ 盏灯所在灯柱的坐标及其亮度。

保证每个灯柱上最多放置两盏灯，即对于任何坐标 $v$，最多只有两个 $i$ 满足 $x_i=v$。

输出格式

输出一个整数，即选择经济型灯泡子集的方案数对 $10^9+7$ 取模后的结果。

样例 1

输入

2
2 3
7 2

输出

3

在第一个样例中，所有三个非空灯泡子集都是正确的。

样例 2

输入

3
1 1
3 1
4 2

输出

6

在第二个样例中，除了集合 $\{1, 2, 3\}$ 以外，所有的灯泡子集都是正确的。

样例 3

输入

5
3 2
4 2
5 2
6 2
7 2

输出

10

样例 4

输入

4
3 2
7 4
7 4
8 2

输出

8

样例 5

输入

5
1 2
1 3
2 1
2 2
4 1

输出

19

数据范围与提示

引入变量 $t$，表示具有相同坐标 $x_i$ 的灯泡的最大数量。

在 $t=1$ 的情况下，$x_1 < x_2 < \ldots < x_n$。

在 $t=2$ 的情况下，$x_1 \le x_2 \le \ldots \le x_n$，且如果 $x_i = x_{i+1}$，则满足 $x_{i-1} < x_i$ 且 $x_{i + 1} < x_{i+2}$（如果对应的灯存在）。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$t$	$n$	附加限制	依赖子任务
$1$	$10$	$t=1$	$n \leq 10$	无	—
$2$	$15$		—	对于任意两盏不同的灯 $i, j$，均满足 $(x_i - s_i \neq x_j)$ 且 $(x_i + s_i \neq x_j - s_j)$
$3$	$15$			对于任意两盏不同的灯 $i, j$，均满足 $(s_i \neq s_j)$
$4$	$15$			对于任意两盏不同的灯 $i, j$，均满足 $(s_i = s_j)$
$5$	$10$		$n \leq 1000$	$(s_i, x_i \leq 1000)$
$6$	$20$		—	无	$1, 2, 3, 4, 5$
$7$	$10$	$t=2$		如果 $(x_i = x_{i+1})$，则满足 $(s_i \neq s_{i+1})$	$1, 2, 3, 4, 5, 6$
$8$	$5$			无	$0, 1 \sim 7$