Luogu P6146 [USACO20FEB] Help Yourself G

佚名 / 2023-05-17 / 原文

发现其实选一条线段 \([l_i, r_i]\) 只跟 \([l_i, r_i]\) 内有没有其他线段有关，便可以发现这条线段的贡献可以单独算出

对于线段 \([l, r]\) 按 \(l\) 升序排序，这样能保证到第 \(i\) 条边时 \(j = i + 1\sim n\) 中没有 \(r_j < l_i\) 的情况
设 \(f_i\) 为前 \(i\) 条线段的所以子集的答案
对于第 \(i\) 条边，有两种情况：“选”或“不选”

不选第 \(i\) 条边
此时答案即为 \(i - 1\) 条边的贡献 \(f_{i - 1}\)
选第 \(i\) 条边
则答案为 \(2\) 部分：\(i - 1\) 条边原有的贡献 \(+\) \([l_i, r_i]\) 没有其他线段产生的新连通块的贡献
第一部分即为 \(f_{i - 1}\)，第二部分转化一下会变为 \(r_j < l_i\) 的所有线段 \(j\) 能产生的所有集合个数
可以对 \(r_i\) 进行前缀和得到 \(s\)，\(m = s_{l_i - 1}\) 即为这部分的数量，答案为这 \(m\) 个元素能产生的集合数量，也就是 \(2^m\)

两种情况加起来就得到了转移方程：\(f_i = f_{i - 1}\times 2 + 2^{s_{l_i - 1}}\)

时间复杂度 \(\mathcal{O}(n\log_2 n)\)

// by lhzawa
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long qpow(long long a, int b) {
    long long tot = 1;
    for (; b; b >>= 1, a = (a * a) % mod) {
        if (b & 1) {
            tot = (tot * a) % mod;
        }
    }
    return tot;
}
const int N = 1e5 + 10;
struct line {
    int l, r;
};
line a[N];
int cmpl(line x, line y) {
    return x.l < y.l;
}
long long dp[N];
int s[2 * N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].l, &a[i].r);
        s[a[i].r]++;
    }
    for (int i = 1; i <= 2 * n; i++) {
        s[i] += s[i - 1];
    }
    sort(a + 1, a + n + 1, cmpl);
    for (int i = 1; i <= n; i++) {
        dp[i] = ((dp[i - 1] << 1) + qpow(2, s[a[i].l - 1])) % mod;
    }
    printf("%lld\n", dp[n]);
    return 0;
}