感觉像是之前做过的题的加强版😅

考虑容斥哪些区间不合法。直接处理比较困难，考虑将所有区间按右端点排序，并将端点离散化（将右端点$+1$，转化为左闭右开区间），设$d{p}_{i,j,k}$表示只考虑前$i$个区间，以及$[1,j)$这段前缀，上一个选择的区间类型是$k\in [0,1]$时的答案。转移如下：

• $d{p}_{i,j,k}\leftarrow d{p}_{i-1,j,k}$
• $d{p}_{i,j,k^{\prime }}\leftarrow -d{p}_{i-1,l_i,k}\times \frac{1}{2^{r_i-l_i}}$，条件：$r_i\le j$，可以是相同类型的区间也可以是不同类型的区间
• $d{p}_{i,j,k}\leftarrow -d{p}_{i-1,j,k}$，条件：$l_i\ge j$，且必须是相同类型区间
• $d{p}_{i,j,k}\leftarrow -d{p}_{i-1,l_i,k}\times \frac{1}{2^{j-l_i}}$，条件：$l_i<j<r_i$，且必须是相同类型区间

最后答案要乘上$2^K$。

显然，这些操作都可以用线段树去维护。

有没有更好的方法？

注意到，第三种转移加上第一种转移是将$\le l_i$的$DP$值推平成$0$，那么我们维护一个指针$p$表示$[1,p]$这段前缀的$DP$值都是$0$，如果$l_i\le p$那么什么都不做；否则我们暴力将指针移动到$l_i$，然后根据转移的范围在差分数组上打标记即可。

复杂度$O(n\log n)$。

$\text{remark}$ 我低估了这道题的思维难度。。。（主要是后半部分）

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define fi first
#define se second
using namespace std;
const int N=4e5+5;
const int mod=1e9+7;
int n,m,K,lsh[N<<1],cnt;
struct node{int l,r,t;bool operator <(const node &a)const{return r<a.r;}
}a[N];
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
int get(int x){return lower_bound(lsh+1,lsh+1+cnt,x)-lsh;
}
int p[2];
ll c[2][N][2];
void add(ll &x,ll y){x=(x+y)%mod;
}
ll calc(int f,int x){return (c[f][x][0]+c[f][x][1]*fpow(mod+1>>1,lsh[x]))%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>K>>n>>m;for(int i=1;i<=n+m;i++){cin>>a[i].l>>a[i].r,a[i].r++,a[i].t=(i<=n);lsh[++cnt]=a[i].l,lsh[++cnt]=a[i].r;}sort(lsh+1,lsh+1+cnt),cnt=unique(lsh+1,lsh+1+cnt)-lsh-1;n+=m;for(int i=1;i<=n;i++)a[i].l=get(a[i].l),a[i].r=get(a[i].r);sort(a+1,a+1+n);c[0][1][0]=c[1][1][0]=1;ll res=1;for(int i=1;i<=n;i++){int l=a[i].l,r=a[i].r,f=a[i].t;if(p[f]>=l)continue;while(p[f]<l){add(c[f][p[f]+1][0],c[f][p[f]][0]);add(c[f][p[f]+1][1],c[f][p[f]][1]);p[f]++;}ll x=calc(f,l),y=-x*fpow(mod+1>>1,lsh[r]-lsh[l])%mod;add(res,y);add(c[f^1][r][0],y);add(c[f][r][0],y);add(c[f][l+1][1],-x*fpow(2,lsh[l]));add(c[f][r][1],x*fpow(2,lsh[l]));}res=res*fpow(2,K)%mod;cout<<(res+mod)%mod;
}