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

思路：

直接枚举区间左端点，用一个cnt数组表示当前端点l,r或者L,R存在1个还是2个或者0个。用一个sum变量记录有多少段区间覆盖了该端点，如果sum==n那么这个端点就有了贡献。

更详细的看代码注释。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
const int N=5e5+7;
const int LINF=1e13+7;
const int MOD=1e9+7;
bool C=0;
vector<int> vec[N*2];
int cnt[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        vec[x*2-1].push_back(i);
        vec[y*2].push_back(i);
        cin>>x>>y;
        vec[x*2-1].push_back(i);
        vec[y*2].push_back(i);
    }
    int res=0; //统计答案
    int sum=0; //当前区间个数（不同i下的），当sum==n的时候代表这个点有贡献
    int now=1; //当前点的贡献
    int ni2=500000004; //1/2在1e9+7下的逆元
    for(int i=1;i<N*2;i++){
        for(auto it:vec[i]){
            if(i%2==1){ //奇数为区间起点
                if(cnt[it]==0){
                    cnt[it]=1;
                    sum++;
                    if(sum==n) res=(res+now)%MOD;
                }
                else{
                    cnt[it]=2;
                    if(sum==n) res=(res+now)%MOD; //先加后乘，因为其中一个在上面加过了
                    now=now*2%MOD;
                }
            }
            else{ //偶数为区间终点
                cnt[it]--;
                if(cnt[it]==0) sum--;
                else now=now*ni2%MOD;
            }
            
        }
    }
    cout<<res<<endl;

}
signed main(){
    IOS;
    int t;
    if(C) cin>>t;
    else t=1;
    while(t--) solve();
}