Help Yourself

题目描述

Bessie 在一维数轴上得到了 $N$ 条线段（$1\le N\le 10^5$）。第 $i$ 条线段包含所有满足 $l_i\le x\le r_i$ 的实数 $x$。 定义一组线段的并集为所有至少被一条线段包含的 $x$ 的集合。定义一组线段的复杂度为其并集中连通区域的数量。 Bessie 想要计算给定这 $N$ 条线段的所有 $2^N$ 个子集中，复杂度之和，并对 $10^9+7$ 取模。 通常，你的工作是帮助 Bessie。但这一次，你就是 Bessie，没有人能帮你。请自助！

输入格式

第一行包含 $N$。 接下来 $N$ 行每行包含两个整数 $l_i$ 和 $r_i$。保证 $l_i< r_i$，并且所有 $l_i,r_i$ 互不相同，且都是在范围 $1 \ldots 2N$ 内的整数。

输出格式

输出答案，对 $10^9+7$ 取模。

3
1 6
2 3
4 5

8

提示

评分： 测试点 2-3 满足 $N\le 16$。 测试点 4-7 满足 $N\le 1000$。 测试点 8-12 没有额外限制。

每个非空子集的复杂度如下所示。

$$\{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1$$$$\{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 2$$$$\{[1,6],[2,3],[4,5]\} \implies 1$$

答案为 $1+1+1+1+1+2+1=8$。 题目致谢：Benjamin Qi

标签: USACO|2020|Gold

来源

USACO|2020|Gold