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();
}
}