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