自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:17:53，当前版本为作者最后更新于2020-03-06 19:25:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先将所有线段按左端点升序排序。

设 $f_i$ 表示前 $i$ 条线段的所有子集的复杂度之和。

如果我们新添加了一条线段，复杂度会怎样变化呢？

1. 不选这条线段。

这种情况下，复杂度没有变化，不包含这条线段的子集的复杂度仍然为 $f_i$。

2. 选这条线段。

复杂度分两部分：原来的复杂度（这部分不会因为新选一条线段而减少，因为线段已经按左端点排好顺序了）和新增加的复杂度（这条线段可能不与已有线段形成连通块）。

原来的复杂度仍然为 $f_i$，而选这条线段可能会让部分子集的复杂度 +1。

如果之前的线段中有 $x$ 条线段不与当前线段相交，则选这 $x$ 条线段的一个子集加上当前线段可以让复杂度在原来子集的复杂度基础上 +1。

根据集合的知识，新增加的复杂度就是 $2^x$。

从而得到递推式：$f_i=f_{i-1}+(f_{i-1}+2^x)=2f_{i-1}+2^x$。

现在的问题就是计算 $x$。

容易看出，设第 $i$ 条线段的左端点为 $l_i$，右端点为 $r_i$，则 $x$ 等于右端点小于 $l_i$ 的线段数量。

我们可以利用前缀和技巧来预处理所有 $x$ 的值。

#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct seg
{
 int l,r;
}a[100005];
int s[200005];
long long f[100005];
bool cmp(const seg&a,const seg&b)
{
 return a.l<b.l;
}
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i].l>>a[i].r;
  s[a[i].r]++;
 }
 sort(a+1,a+n+1,cmp);
 for(int i=1;i<=2*n;i++)
  s[i]+=s[i-1];
 for(int i=1;i<=n;i++)
  f[i]=(2*f[i-1]+fpow(2,s[a[i].l-1]))%MOD;
 cout<<f[n]<<endl;
 return 0;
}