题意：平面上一共有k个硬币(k<=1e9)，给你n个区间这些区间中至少有一个硬币反面朝上，m个区间中至少有一个硬币正面朝上。问有多少种硬币放置方案？n,m<=100005.
标程：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int mod=1e9+7; 4 const int N=400005; 5 typedef long long ll; 6 struct node{int l,r;}a[N],b[N]; 7 int k,n,m,p[N],rg[N][2],g[3],f[N][3],t; 8 int ksm(int x,int y) 9 { 10 int res=1; 11 while (y){if (y&1) res=(ll)res*x%mod; x=(ll)x*x%mod;y>>=1;} 12 return res; 13 } 14 int main() 15 { 16 scanf("%d%d%d",&k,&n,&m); 17 for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),p[++t]=--a[i].l,p[++t]=a[i].r; 18 for (int i=1;i<=m;i++) scanf("%d%d",&b[i].l,&b[i].r),p[++t]=--b[i].l,p[++t]=b[i].r; 19 p[++t]=0;p[++t]=k; 20 sort(p+1,p+t+1);t=unique(p+1,p+t+1)-p-1; 21 for (int i=1;i<=t;i++) rg[i][0]=rg[i][1]=t+1; 22 for (int i=1;i<=n;i++) 23 { 24 a[i].l=lower_bound(p+1,p+t+1,a[i].l)-p; 25 a[i].r=lower_bound(p+1,p+t+1,a[i].r)-p; 26 rg[a[i].l][0]=min(rg[a[i].l][0],a[i].r); 27 } 28 for (int i=1;i<=m;i++) 29 { 30 b[i].l=lower_bound(p+1,p+t+1,b[i].l)-p; 31 b[i].r=lower_bound(p+1,p+t+1,b[i].r)-p; 32 rg[b[i].l][1]=min(rg[b[i].l][1],b[i].r); 33 } 34 for (int i=t-1;i>=0;i--) rg[i][0]=min(rg[i][0],rg[i+1][0]),rg[i][1]=min(rg[i][1],rg[i+1][1]); 35 f[t][0]=f[t][1]=f[t][2]=1; 36 for (int i=t-1;i>=1;i--) 37 { 38 g[2]=(ll)f[i+1][2]*(ksm(2,p[i+1]-p[i])-2+mod)%mod;//这一段有0有1 39 for (int j=0;j<=1;j++) g[j]=((ll)f[i+1][j]-f[rg[i][j]][j]+mod)%mod;//g[1/0]表示这一段全0/1且符合限制的方案数。 40 f[i][0]=((ll)f[i+1][0]+g[1]+g[2])%mod; 41 f[i][1]=((ll)f[i+1][1]+g[0]+g[2])%mod; 42 f[i][2]=((ll)g[0]+g[1]+g[2])%mod; 43 } 44 printf("%d ",f[1][2]); 45 return 0; 46 }
易错点：1.离散化数组的大小需要注意，此题应该开4倍。
2.注意左端点要-1，因而统计的时候都是左开右闭的区间。
题解：前缀和优化dp
朴素思路：将区间按照左端点排序，dp[i:走到第i个格子][j:满足前j个0区间][k:满足前k个1区间]。状态数太大。
可以按照端点离散化，之后就可以按照关键点跳。官方题解:dp0[i][l1]表示最后一个位置为0，当前统计完前i个关键点，l1表示上一个1的位置在哪个关键点区间，dp1同设。状态数还是太大。
继续优化：中间部分按照全1，全0，有1有0讨论。后面两维可以合并掉。f[i:走到第i个关键点，后面的所有关键点都满足其开头限制][0/1:pos[i]~pos[i+1]的区间包含0/1（最后一个0/1在i区间），2:全集]的方案数。f[i][0/1]是最后一个0/1在i~t区间的方案后缀和。f[i][2]是当前的最后一段有0有1的方案数全集（不是后缀和）。
对于限制的处理，对于有相同左端点的区间，取右端点min。对于有包含关系的区间，两个限制都取较小的一个右端点，保证右端点单调，可以直接避免最靠前的一个01位置的不合法情况。
O((n+m)logk)。