链接 & 题目大意

P6146 Help Yourself G

算法 & 数据结构

计数，DP

思路 & 推导过程

首先可以考虑如果把一个线段加进去会出现什么事情。
我们先想到可以考虑 dp[i] 为包含第 i 个线段的答案为多少，但是发现这样会算重，很难处理。

那只能换个思路，也就是令 dp[i] 表示加了这个线段后的答案。
把一个线段加进去，那么之前的那些集合会保留，而且之前的那些集合都还会对应着增加一个含有目前线段的集合，所以先把答案 $\times 2$，然后注意到如果对于之前的某个集合，之前的所有线段和新的线段都不相交，那么这个集合的答案就会 $+1$，如果我们假设之前有 $x$ 个线段和目前的这个线段不相交，那么答案会增加 $2^x$。

所以我们就做完了，我们可以先按左端点排序，然后每次新加一个线段。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
*/
int n, dp[1000005], dp2[1000005];
struct node {
    int l, r;
} a[1000005];
int mod = 1e9 + 7;
bool cmp(node x, node y) {
    // return x.l < y.l;
    if (x.l == y.l) return x.r < y.r;
    else return x.l < y.l;
}
int t[1000005];
int lowbit(int x) {return x & (-x);}
void add(int x, int y) {
    for (; x <= n * 2; x += lowbit(x)) t[x] += y;
}
int query(int x) {
    int ans = 0;
    for (int i = x; i >= 1; i -= lowbit(i)) {
        ans += t[i];
    }
    return ans;
}
int p[1000005];
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i].l >> a[i].r, add(a[i].r, 1);
    sort(a + 1, a + n + 1, cmp);
    int ans = 0;
    // for (int l = 1; l <= n; l ++) {
    //     for (int r = l; r <= n; r ++) {
    //         int lst = a[l].r, cnt = 1;
    //         for (int i = l + 1; i <= r; i ++) {
    //             if (a[i].l > lst) {
    //                 cnt ++, lst = a[i].r;
    //             }
    //         }
    //         ans += cnt;
    //         cout << l << " " << r << " " << cnt << "\n";
    //     }
    // }
    p[0] = 1;
    for (int i = 1; i <= n; i ++) {
        p[i] = p[i - 1] * 2ll;
        p[i] %= mod;
    }
    for (int i = 1; i <= n; i ++) {
            int tmp = 0;
            dp[i] += dp[i - 1] * 2;
            tmp = query(a[i].l);
            // for (int j = 1; j < i; j ++) {
                // if (a[j].r < a[i].l) tmp ++;
            // }
            // cout << tmp << "\n";
        // for (int j = 1; j < i; j ++) {
        //     // dp[i] += dp[j];
        //     if (a[j].r >= a[i].l) ;
        //     else {
        //         tmp ++;
        //         // int x = 1;
        //         // for (int k = 1; k < j; k ++) {
        //         //     if (a[k].r < a[i].l) x += dp[k];
        //         // }
        //         // dp[i] += dp[j] + x;
        //     }
        // }
        // dp[i] ++;
        
        dp[i] += p[tmp];
        dp[i] %= mod;
        // cout << dp[i] << ' ' << i << " " << tmp << "\n";
    }
    cout << dp[n];
    // cout << ans;
    return 0;
}