#PU1018. USACO 2020 February Contest, Gold — Problem 2. Help Yourself

    ID: 1164 传统题 文件IO:help 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb20来源:usaco.orgscoring:equal_test_cases枚举线段树

USACO 2020 February Contest, Gold — Problem 2. Help Yourself

USACO 2020 February Contest, Gold — Problem 2. Help Yourself

题目描述

Bessie has been given NN segments (1≤N≤1051\le N\le 10^5) on a 1D number line. The

iith segment contains all reals xx such that li≤x≤ril_i\le x\le r_i.

Define the

union

of a set of segments to be the set of all xx that are

contained within at least one segment. Define the

complexity

of a set of

segments to be the number of connected regions represented in its union.

Bessie wants to compute the sum of the complexities over all 2N2^N subsets of

the given set of NN segments, modulo 109+710^9+7.

Normally, your job is to help Bessie. But this time, you are Bessie, and there's

no one to help you. Help yourself!

输入格式

The first line contains NN.

Each of the next NN lines contains two integers lil_i and rir_i. It is

guaranteed that li<ril_i< r_i and all li,ril_i,r_i are distinct integers in the range

1…2N.1 \ldots 2N.

输出格式

(见题面原文)

数据范围

Test cases 2-3 satisfy N≤16N\le 16.

Test cases 4-7 satisfy N≤1000N\le 1000.

Test cases 8-12 satisfy no additional constraints.

样例

样例 1

3

1 6

2 3

4 5
8

The complexity of each nonempty subset is written below.

$$\{[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$$

The answer is $1+1+1+1+1+2+1=8$.

Problem credits: Benjamin Qi