先按左端点从小到大排序。
设 \(f(i)\) 表示前 \(i\) 条线段的所有子集的复杂度之和。
考虑从 \(f(i-1)\) 转移到 \(f(i)\)，即考虑新加进来第 \(i\) 条线段的过程。第 \(i\) 条线段加进来所新产生的贡献分两种：
-
设除了第 \(i\) 条线段选中的线段集合为 \(S\)，则若 \(S\) 中存在一条线段与第 \(i\) 条线段有交，即不产生新的复杂度。
-
反之，若 \(S\) 中所有线段都和 \(i\) 没有交（即 \(\forall j\in S,r_j<l_i\)），此时产生 \(1\) 的新复杂度。
容易推出第 \(i\) 条线段产生的复杂度为 \(f(i-1)+2^{cnt}\)，其中 \(cnt\) 为第 \(1\sim i-1\) 条线段中与第 \(i\) 条线段没有交的线段条数。所以 \(f(i)=2f(i-1)+2^{cnt}\)。
计算 \(cnt\) 就在每个右端点处打个标记然后前缀和一下即可。
时间复杂度 \(O(n\log n)\)，瓶颈在排序。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,P=1e9+7;
int n,pre[N<<1],dp[N];
pii a[N];
int qpow(int x,int p){
int res=1;
while(p){
if(p&1){
res=1LL*res*x%P;
}
x=1LL*x*x%P;
p>>=1;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].first,&a[i].second);
pre[a[i].second]++;
}
sort(a+1,a+n+1);
for(int i=1;i<=n*2;i++){
pre[i]+=pre[i-1];
}
for(int i=1;i<=n;i++){
dp[i]=(2LL*dp[i-1]%P+qpow(2,pre[a[i].first-1]))%P;
}
printf("%d",dp[n]);
return 0;
}