#CW34. 线段并集的连通块(segmentcraft)
线段并集的连通块(segmentcraft)
题目描述
数轴上放着 条闭区间。第 条区间的两个端点为 和 ,它覆盖数轴上从 到 的所有点。任意两个端点的位置都不相同。
小 W 可以任选一些区间,把所选区间覆盖到的所有点合并成一个集合。我们关心这个集合在数轴上被分成了多少段互不相连的部分:
- 如果没有选择任何区间,集合为空,记作有 个连通块;
- 如果选择的区间有交叠,或者一个区间的右端点严格大于另一个区间的左端点,那么它们属于同一个连通块;
- 只有当两个相邻部分之间存在一段没有被覆盖的空隙时,它们才是不同的连通块。
例如, 与 的并集是 ,只有 个连通块;而 与 之间有空隙,它们的并集有 个连通块。
请计算所有 种选择方案的连通块数量之和。由于答案可能很大,请将结果对 取模。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示第 条区间。保证 ,且任意两个端点的位置都不相同。
输出格式
输出一个整数,表示所有选择方案的连通块数量之和对 取模的结果。
样例 1 输入
3
1 6
2 3
4 5
样例 1 输出
8
样例 1 说明
只选择一条区间时,三种方案各有 个连通块。选择 与另外任意一条区间时,并集仍然只有 个连通块;选择 和 时,两段之间有空隙,因此有 个连通块。三条区间全部选择时并集为 ,有 个连通块。加上空集的贡献 ,总和为 。
数据范围
所有数据满足 。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 20 | ||
| B | 30 | ||
| C | 10 | 所有线段两两不相交 | |
| D | 所有线段有公共交点 | ||
| E | 30 | 无附加限制 |