当前位置：首页 > news >正文

打卡信奥刷题（2995）用C++实现信奥题 P6146 [USACO20FEB] Help Yourself G

news 2026/3/26 17:26:23

P6146 [USACO20FEB] Help Yourself G

题目描述

在一个数轴上有NNN条线段，第iii条线段覆盖了从lil_ili到rir_iri的所有实数（包含lil_ili和rir_iri）。

定义若干条线段的并为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的复杂度为这些线段的并形成的连通块的数目。

现在 Bessie 想要求出给定NNN条线段的所有子集（共有2N2^N2N个）的复杂度之和对109+710^9+7109+7取模的结果。

你也许猜到了，你需要帮 Bessie 解决这个问题。但不幸的是，你猜错了！在这道题中你就是 Bessie，而且没有人来帮助你。一切就靠你自己了！

输入格式

第一行一个整数NNN（1≤N≤1051 \leq N \leq 10^51≤N≤105）。

接下来NNN行，每行两个整数li,ril_i,r_ili,ri，描述一条线段。保证1≤li<ri≤2N1 \leq l_i \lt r_i \leq 2N1≤li<ri≤2N，且任意两个端点都不在同一位置上。

输出格式

输出所求答案对109+710^9+7109+7取模的结果。

输入输出样例 #1

输入 #1

3 1 6 2 3 4 5

输出 #1

说明/提示

样例解释

所有非空子集的复杂度如下所示（显然空集的复杂度为零）：
{[1,6]} ⟹ 1,{[2,3]} ⟹ 1,{[4,5]} ⟹ 1 \{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1{[1,6]}⟹1,{[2,3]}⟹1,{[4,5]}⟹1

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

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

故答案为1+1+1+1+1+2+1=81+1+1+1+1+2+1=81+1+1+1+1+2+1=8。

子任务

测试点2∼32 \sim 32∼3满足N≤16N \leq 16N≤16；
测试点4∼74 \sim 74∼7满足N≤1000N \leq 1000N≤1000；
测试点8∼128 \sim 128∼12没有特殊限制。

C++实现

#include<iostream>#include<algorithm>#defineMOD1000000007usingnamespacestd;structseg{intl,r;}a[100005];ints[200005];longlongf[100005];boolcmp(constseg&a,constseg&b){returna.l<b.l;}longlongfpow(longlongx,longlongy){longlongans=1;while(y){if(y&1)ans=ans*x%MOD;x=x*x%MOD;y>>=1;}returnans;}intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i].l>>a[i].r;s[a[i].r]++;}sort(a+1,a+n+1,cmp);for(inti=1;i<=2*n;i++)s[i]+=s[i-1];for(inti=1;i<=n;i++)f[i]=(2*f[i-1]+fpow(2,s[a[i].l-1]))%MOD;cout<<f[n]<<endl;return0;}