Help Yourself (USACO Gold 2020 February)

每一个线段 $i$ 对应 $2^{n-1}$ 个包含这个线段的组合，对于其中一部分没有和 $i$ 重合的组合，对复杂度的贡献全都是 $1$ . 对于有重合的组合，可以认为当 $i$ 处于重合最左侧时贡献为 $1$ ，非最左侧时贡献为0。所以答案就是 $n \cdot 2^{n-1} - \sum_i C_i$ ，其中 $C_i$ 是 $i$ 不在重合最左侧的组合数量。

为了求 $C_i$ ，我们可以预处理每个线段的“左侧重合线段”的数量 $x_i$ ，则 $C_i = 2^{n-1} - 2^{n-1-x_i}$ 。

将线段按左端点从小到大排序之后，用优先队列可以得到左侧重合线段数 $x_i$ 。

复杂序是 $\mathcal{O}(N)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
vector<pair<int,int>> segs;
int x[100005];
const int MOD = 1e9 + 7;
priority_queue<int, vector<int>, greater<int>> q;   // small top priority queue
int ans;
 
int modpow(int a, int b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    int u = modpow(a, b/2);
    int r = ((ll)u*u) % MOD;
    if (b % 2 == 1)
        r = (ll)r * a % MOD;
    return r;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int l,r;
        scanf("%d %d", &l, &r);
        segs.push_back({l,r});
    }
    sort(segs.begin(), segs.end());
 
    for (int i = 0; i < n; i++) {
        int l = segs[i].first, r = segs[i].second;
        while (!q.empty() && q.top() < l) {
            q.pop();
        }
        x[i] = q.size();
        q.push(r);
    }
 
    int two_n_1 = modpow(2, n-1);   // 2^(n-1)
    ans = (ll)n * two_n_1 % MOD;
    for (int i = 0; i < n; i++) {
        int neg = ((ll)two_n_1 + MOD - modpow(2, n-1-x[i])) % MOD;
        ans = ((ll)ans + MOD - neg) % MOD;
    }
    printf("%d", ans);
 
    return 0;
}