2023牛客暑期多校训练营9-Non-Puzzle: Segment Pair

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

题目大意

解题思路

对于每一对$[l_i,r_i]$和$[l_i^{\prime },r_i^{\prime }]$，其有三种贡献：重叠部分贡献为$2$，各自的不重叠部分贡献为$1$，其他部分贡献为$0$，我们可以差分求出第$i$对对于某一段的贡献，设$cn{t}_{0/1/2}$分别表示有几对的贡献为$0/1/2$，则显然在有重合的情况下，方案数为$2^{cn{t}_2}$，求解即可。

代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=5e5+5,mod=1e9+7;
int n,l1,r1,l2,r2,a[N],b[3],p[N];
struct node{int x,y,id;
};
vector<node>ve;
bool cmp(node a,node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;
}
int main(){cin>>n;p[0]=1;for(int i=1;i<=n;i++)p[i]=p[i-1]*2ll%mod;for(int i=1;i<=n;i++){cin>>l1>>r1>>l2>>r2;ve.pb({l1,1,i});ve.pb({r1+1,-1,i});ve.pb({l2,1,i});ve.pb({r2+1,-1,i});}sort(ve.begin(),ve.end(),cmp);b[0]=n;long long ans=0;for(auto v:ve){b[a[v.id]]--;a[v.id]+=v.y;if(v.y==1&&!b[0])ans+=p[b[2]],ans%=mod;b[a[v.id]]++;}cout<<ans;
}