#CW34. 线段并集的连通块(segmentcraft)

线段并集的连通块(segmentcraft)

题目描述

数轴上放着 nn 条闭区间。第 ii 条区间的两个端点为 lil_i 和 rir_i,它覆盖数轴上从 lil_i 到 rir_i 的所有点。任意两个端点的位置都不相同。

小 W 可以任选一些区间,把所选区间覆盖到的所有点合并成一个集合。我们关心这个集合在数轴上被分成了多少段互不相连的部分:

  • 如果没有选择任何区间,集合为空,记作有 00 个连通块;
  • 如果选择的区间有交叠,或者一个区间的右端点严格大于另一个区间的左端点,那么它们属于同一个连通块;
  • 只有当两个相邻部分之间存在一段没有被覆盖的空隙时,它们才是不同的连通块。

例如,[1,3][1,3] 与 [2,5][2,5] 的并集是 [1,5][1,5],只有 11 个连通块;而 [1,2][1,2] 与 [4,5][4,5] 之间有空隙,它们的并集有 22 个连通块。

请计算所有 2n2^n 种选择方案的连通块数量之和。由于答案可能很大,请将结果对 109+710^9+7 取模。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 li,ril_i,r_i,表示第 ii 条区间。保证 1≤li<ri≤2n1 \le l_i < r_i \le 2n,且任意两个端点的位置都不相同。

输出格式

输出一个整数,表示所有选择方案的连通块数量之和对 109+710^9+7 取模的结果。

样例 1 输入

3
1 6
2 3
4 5

样例 1 输出

8

样例 1 说明

只选择一条区间时,三种方案各有 11 个连通块。选择 [1,6][1,6] 与另外任意一条区间时,并集仍然只有 11 个连通块;选择 [2,3][2,3] 和 [4,5][4,5] 时,两段之间有空隙,因此有 22 个连通块。三条区间全部选择时并集为 [1,6][1,6],有 11 个连通块。加上空集的贡献 00,总和为 88。

数据范围

所有数据满足 1≤n≤1000001 \le n \le 100000。

数据类别 分值 测试点 附加条件
A 20 1∼51\sim 5 n≤16n \le 16
B 30 6∼136\sim 13 n≤1000n \le 1000
C 10 14∼1514\sim 15 所有线段两两不相交
D 16∼1916\sim 19 所有线段有公共交点
E 30 2020 无附加限制