【题解】LuoGu6146：[USACO20FEB]Help Yourself G

原题传送门
把线段按照左端点排序
然后令$d{p}_i$表示第$i$条线段为止的答案
$d{p}_i=2\ast d{p}_{i-1}+2^k$
$k$表示之前有多少条线段与自己没有交，这个可以用树状数组维护一下

Code：

#include <bits/stdc++.h>
#define maxn 100010
#define LL long long
using namespace std;
const LL qy = 1000000007;
LL ans;
struct data{
	int l, r;
}a[maxn];
int n, tree[maxn << 1];
LL dp[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(data x, data y){ return x.l == y.l ? x.r < y.r : x.l < y.l; }
int lowbit(int x){ return x & -x; }
void update(int x, int y){ for (; x <= 2 * n; x += lowbit(x)) tree[x] += y; }
int query(int x){ int s = 0; for (; x; x -= lowbit(x)) s += tree[x]; return s; }

LL ksm(LL n, LL k){
	LL s = 1;
	for (; k; k >>= 1, n = n * n % qy) if (k & 1) s = s * n % qy;
	return s;
}

int main(){
	freopen("help.in", "r", stdin);
	freopen("help.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; ++i) a[i].l = read(), a[i].r = read();
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; ++i){
		dp[i] = (dp[i - 1] * 2 % qy + ksm(2, i - 1 - query(a[i].l))) % qy;
		update(a[i].l, 1), update(a[i].r + 1, -1);
	}
	printf("%lld\n", dp[n]);
	return 0;
}