Non-Puzzle: Segment Pair

题意

给n对区间，要求每对区间恰好选一个使得选出来的n个区间有交集，问有多少方案数

1≤n,l1,l2,r1,r2≤5×10^5

思路

枚举结果以i为左端点的区间的数量,对于每个i,以i为左端点的区间的数量=结果包含i的数量-结果同时包含i和i-1的数量.

对于每对区间,如果两个区间没有重叠部分,那么这对线段对区间内的每个点贡献*1,对区间外的每个点贡献*0,就是不管怎么选也选不到外面的点,就直接*0.

如果有重叠,重叠部分对区间内的每个点贡献*2,就是如果选重叠里面的点,都会有2种选择,所以*2.

需要区间修改和单点查询,使用树状数组维护

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const long long mxn=5e5;
long long num[mxn+10],f[mxn+10];//树状数组,num为结果包含i的方案数量,f非0时表示不存在包含i的方案,即线段对贡献*0的个数
long long num2[mxn+10],f2[mxn+10];//树状数组,num为结果同时包含i和i-1的方案数量,f非0时表示不存在同时包含i和i-1的方案,即线段对贡献*0的个数
long long mi[mxn+10];//2^i
long long lowbit(long long i)
{
    return i&(-i);
}
void add(long long flag,long long i,long long x)//更新num,f
{
    if(flag==1)
        while(i<=mxn)
        {
            num[i]+=x;
            i+= lowbit(i);
        }
    else if(flag==2)
        while(i<=mxn)
        {
            f[i]+=x;
            i+= lowbit(i);
        }
}
void add2(long long flag,long long i,long long x)//更新num2,f2
{
    if(flag==1)
        while(i<=mxn)
        {
            num2[i]+=x;
            i+= lowbit(i);
        }
    else if(flag==2)
        while(i<=mxn)
        {
            f2[i]+=x;
            i+= lowbit(i);
        }
}
long long getsum(long long flag,long long i)//获取结果包含i的方案数量
{
    long long ans=0;
    if(flag==1)
        while(i)
        {
            ans+=num[i];
            i-= lowbit(i);
        }
    else if(flag==2)
        while(i)
        {
            ans+=f[i];
            i-= lowbit(i);
        }
    return ans;
}
long long getsum2(long long flag,long long i)//获取结果同时包含i和i-1的方案数量
{
    long long ans=0;
    if(flag==1)
        while(i)
        {
            ans+=num2[i];
            i-= lowbit(i);
        }
    else if(flag==2)
        while(i)
        {
            ans+=f2[i];
            i-= lowbit(i);
        }
    return ans;
}
void solve()
{
    long long n;
    cin>>n;
    mi[0]=1;
    for(long long i=1;i<=mxn+6;i++)
    {
        mi[i]=mi[i-1]*2;
        mi[i]%=mod;
    }
    for(long long i=1;i<=n;i++)
    {
        long long l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(l1>l2)
        {
            swap(l1,l2);
            swap(r1,r2);
        }
        if(l1==l2)//保证左线段在左边
        {
            if(r1>r2)
                swap(r1,r2);
        }
        if(r1>=l2)//有重叠
        {
            add(1,max(l1,l2),1);
            add(1,min(r2,r1)+1,-1);//重叠部分有i的数量+1
            add2(1,max(l1,l2)+1,1);
            add2(1,min(r2,r1)+1,-1);//重叠部分同时有i和i-1的数量+1
        }
        else//无重叠
        {
            add(2,r1+1,1);
            add(2,l2,-1);//中间因为不存在,贡献*0的数量+1
            add2(2,r1+1,1);
            add2(2,l2+1,-1);//中间因为不存在,贡献*0的数量+1
        }
        //两边不存在,贡献*0的数量+1
        add(2,1,1);
        add(2,min(l1,l2),-1);
        add(2,max(r2,r1)+1,1);
        add(2,mxn+1,-1);
        add2(2,1,1);
        add2(2,min(l1,l2)+1,-1);
        add2(2,max(r2,r1)+1,1);
        add2(2,mxn+1,-1);
    }
    long long sum=0;
    for(long long i=1;i<=mxn;i++)//枚举左端点,数量=包含i数量-同时包含i和i-1的数量
    {
        if(getsum(2,i)==0)//如果结果同时包含i的方案存在
        {
            sum+=mi[getsum(1,i)];//加上包含i的方案数量
            sum%=mod;
            if(getsum2(2,i)==0)//如果结果同时包含i和i-1的方案存在
                sum-=mi[getsum2(1,i)];//减去结果同时包含i和i-1的方案数量,相当于最后sum加上以i开头的区间数量
            while(sum<0) sum+=mod;
            sum%=mod;
        }
    }
    cout<<sum<<endl;
}
signed main()
{
    long long _;
    _=1;
//    cin>>_;
    while(_--) solve();
}