题解 | I Non-Puzzle: Segment Pair

Non-Puzzle: Segment Pair

https://ac.nowcoder.com/acm/contest/57363/I

也许更好的阅读体验

Description\mathcal{Description}

nn对区间,要求每对区间恰好选一个使得选出来的nn个区间有交集,问有多少方案数 1n,li,ri5×1051\le n, l_i,r_i\le 5×10^5

Solution\mathcal{Solution}

注意到区间的值域也是5×1055×10^5,考虑从值域入手,也就是枚举每个点看有多少种方案使最后的交集包含这个点

设有kk对区间的两个区间都包含这个点,那么就有2k2^k种方案

显然,这样的方案会算重,因为不同的点可能对应相同的选择方案,考虑当前枚举的点是ii,假设i1i-1对应的方案数为2m2^m,如果点ii相比点i1i-1没有新增的区间,也没有减少区间,那么iii1i-1方案数是完全一样的,如果iii1i-1新增了一些区间并没有减少区间,那么ii对应的方案数是包含了i1i-1对应的方案数的,新增的方案数是二者的差2k2m2^k-2^m,而如果减少了一些区间,那么我们记减少了后对应的方案数为2p2^p,新增的方案数仍然是二者的差2k2p2^k-2^p,我们只需维护这个过程即可,总复杂度O(n)O(n)

Code\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;
}

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

全部评论
啊?大佬竟是同机房选手
1
送花
回复 分享
发布于 2023-08-15 09:40 天津

相关推荐

23 收藏 评论
分享
牛客网
牛客企业服务