Non-Puzzle: Segment Pair

Non-Puzzle: Segment Pair
时间限制(普通/Java):2000MS/4000MS 内存限制:262144KByte

描述

输入

输出

样例输入

3
1 4 6 7
2 5 3 5
1 3 5 7

样例输出

2

思路

枚举区间左端点 x，则要满足区间的交包含x，并且不包含 x − 1。

考虑计算包含 x 的方案数，则每对区间的贡献为0，1 或 2（代表有几个区间包含点 x)，方案数就是所有贡献的乘积。

然后要扣除包含 x − 1 的方案数。实质上扣除的是同时包含 x 和 x − 1两个点的方案数，同样是若干个 0, 1, 2 的乘积。

对 x 作扫描线，实时维护 0, 1, 2 的个数。

AC代码

#include <bits/stdc++.h>
using namespace std;
int mod=1e9+7;
vector<int>v1[500005],v2[500005];
int t[500005],p2[500005];
void solve()
{
    int n,ans=0,sum=0,now=0;
    cin>>n;
    p2[0]=1;
    for(int i=1;i<=n;i++)
        p2[i]=p2[i-1]*2%mod;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        v1[a].push_back(i);
        v2[b].push_back(i);
        cin>>a>>b;
        v1[a].push_back(i);
        v2[b].push_back(i);
    }
    for(int i=1;i<500005;i++)
    {
        for(int j : v1[i])
        {
            t[j]++;
            if(t[j]==1) sum++;
            if(sum==n) (ans+=p2[now])%=mod;
            if(t[j]==2) now++;
        }
        for(int j : v2[i])
        {
            t[j]--;
            if(t[j]==0) sum--;
            if(t[j]==1) now--;
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)
    {
        solve();
    }
}