23牛客多校9 I Non-Puzzle: Segment Pair

也许更好的阅读体验

\(\mathcal{Description}\)
给\(n\)对区间，要求每对区间恰好选一个使得选出来的\(n\)个区间有交集，问有多少方案数
\(1\le n, l_i,r_i\le 5×10^5\)

\(\mathcal{Solution}\)
注意到区间的值域也是\(5×10^5\)，考虑从值域入手，也就是枚举每个点看有多少种方案使最后的交集包含这个点
设有\(k\)对区间的两个区间都包含这个点，那么就有\(2^k\)种方案
显然，这样的方法会算重，因为不同的点可能对应相同的选择方案，考虑当前枚举的点是\(i\)，假设\(i-1\)对应的方案数为\(2^m\)，如果点\(i\)相比点\(i-1\)没有新增的区间，也没有减少区间，那么\(i\)和\(i-1\)方案数是完全一样的，如果\(i\)比\(i-1\)新增了一些区间并没有减少区间，那么\(i\)对应的方案数是包含了\(i-1\)对应的方案数的，新增的方案数是二者的差\(2^k-2^m\)，而如果减少了一些区间，那么我们记减少了后对应的方案数为\(2^p\)，新增的方案数仍然是二者的差\(2^k-2^p\)，我们只需维护这个过程即可，总复杂度\(O(n)\)

\(\mathcal{Code}\)

#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int n, k, ans;
int num[maxn], mi[maxn];
vector <int> in[maxn], out[maxn];
int mo (int x)
{
    if (x >= mod)   return x - mod;
    return x;
}
int main ()
{
    scanf("%d", &n);
    mi[0] = 1;
    for (int i = 1; i <= n; ++i)    mi[i] = mo(mi[i - 1] << 1);
    for (int i = 1, l, r; i <= n; ++i) {
        scanf("%d%d", &l, &r);
        in[l].push_back(i), out[r + 1].push_back(i);
        scanf("%d%d", &l, &r);
        in[l].push_back(i), out[r + 1].push_back(i);
    }
    int tot = 0, mx = 500000, lst = mx + 1;
    for (int i = 1; i <= mx; ++i) {
        for (int v : out[i]) {
            if (num[v] == 2)    --k;
            --num[v];
            if (!num[v])    --tot;
        }
        if (tot < n)	lst = mx + 1;
        else	lst = k;
        for (int v : in[i]) {
            if (!num[v])    ++tot;
            ++num[v];
            if (num[v] == 2)    ++k;
            if (tot == n) {
				if(lst == mx + 1 || k > lst)    ans = mo(mo(ans + mod - mi[lst]) + mi[k]);
				lst = k;
			}
        }
    }
    printf("%d\n", ans);
    return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧