洛谷 P6146 [USACO20FEB]Help Yourself G

传送门
先把所有线段按照左端点从小到大排序。
考虑一个dp
当加入一条线段之后
$$f_i=2\ast f_{i-1}+2^x$$
其中，x为这条线段左面有多少条线段没有和他有交点；f表示到第i条线段，复杂度是多少，我们对于第i条线段，可以不选，那么还是f_i-1，如果选了，那么对于总复杂度影响就是f_i-1+2^x,然后用前缀和处理一下X，快速幂乱跑一下就阔以辣

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define int long long 
using namespace std;
const int modd=1e9+7;
int n;
int sum[200005],f[100005];
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
} 
struct NODE{
   
	int x,y;
}zhn[100005]; 
inline bool cmp(NODE a,NODE b){
   
	return a.x<b.x;
}
inline int ksm(int a,int b){
   //a的b次方 
	int ans=1;
	while(b){
   
		if(b&1) ans=ans*a%modd;
		a=a*a%modd;
		b>>=1;
	} 
	return ans%modd;
}
main(){
   
	n=read();
	for(int i=1;i<=n;i++){
   
	    zhn[i].x=read();
		zhn[i].y=read(); 
		sum[zhn[i].y]++;
	}
	for(int i=1;i<=2*n;i++)sum[i]+=sum[i-1];
	sort(zhn+1,zhn+n+1,cmp);
// f[0]=0;
	for(int i=1;i<=n;i++){
   
		f[i]=(2*f[i-1]%modd+ksm(2,sum[zhn[i].x-1])%modd)%modd; 
	}
	printf("%lld",(f[n]%modd+modd)%modd);
	return 0;
}