2023 牛客多校 9 I - Non-Puzzle: Segment Pair 题解

首先我们考虑某一个点被所有线段覆盖的方案数：如果一对线段中有只有一条线段能覆盖这个点，那么我们就只能选这条线段，如果两条线段都能覆盖这个点，我们可以任选其一。但是题目要求的是存在一个点被所有线段覆盖，如果我们对数轴上的每一个点求方案数的话，其中必然有重复的方案，我们考虑什么样的情况方案会重复。不难发现，对于两个点，如果覆盖第一个点的线段的集合与覆盖第二个点的线段的集合相同的话，这两个点所对应的方案的集合是相同的。反之，这两个点对应的情况是不同的，具体来说有两种情况：

存在一对线段，一个点只被其中的一条线段覆盖，而另一个点只被另一条线段覆盖。这两个点所对应的方案的集合是不交的。
否则，存在一对线段，一个点只被其中的一条线段覆盖，而另一个点只被两条线段覆盖。一个点所对应的方案的集合是另一个点对应的集合的子集。

于是我们在每次线段覆盖情况变化的时候计算当前的方案数并加入到答案中。我们可以把每条线段 $[l, r]$ 拆成两个事件：

在 $l$ 处线段覆盖开始
在 $r + 1$ 处线段覆盖结束

我们将所有事件排序，从小到大遍历就可以得到所有线段覆盖的情况。遍历的过程中维护 $num_i, i=0,1,2$ 为一对线段中有 $i$ 条线段覆盖当前点的线段对的数量。

注意到线段覆盖变化有四种情况：

有一对线段从零条覆盖变成了一条覆盖，此时如果 $num_0 = 0$ 我们应把答案加上 $2^{num_2}$
有一对线段从一条覆盖变成了两条覆盖，还记得我们上面说的第二种情况吗？由于子集的方案数已经加到答案里了，此时如果 $num_0 = 0$ 我们应把答案加上 $2^{num_2 - 1}$
有一对线段从两条覆盖变成了一条覆盖，答案已经计算过了，跳过
有一对线段从一条覆盖变成了零条覆盖，不符合被所有线段覆盖的条件，跳过

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
 
    constexpr int mod = 1e9 + 7;
    vector<int> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * 2 % mod;
    }
 
    vector<array<int, 3>> a;
    for (int i = 0; i < n; i++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        a.push_back({l1, 1, i});
        a.push_back({r1 + 1, -1, i});
        a.push_back({l2, 1, i});
        a.push_back({r2 + 1, -1, i});
    }
 
    sort(begin(a), end(a));
 
    array<int, 3> num{n, 0, 0}; // 题解里提到的
    vector<int> cnt(n); // 每一对线段中当前有几条覆盖
    int ans = 0;
 
    for (auto [x, f, i] : a) {
        num[cnt[i]]--;
        cnt[i] += f;
        num[cnt[i]]++;
 
        if (f == 1 && num[0] == 0) {
            if (cnt[i] == 2) { // 从一条覆盖变成两条覆盖
                ans = (ans + pw[num[2] - 1]) % mod;
            } else { // 从零条覆盖变成一条覆盖
                ans = (ans + pw[num[2]]) % mod;
            }
        }
    }
 
    cout << ans << endl;
    return 0;
}

2023 牛客多校 9 I - Non-Puzzle: Segment Pair 题解

代码