【学习笔记】CF930E Coins Exhibition

本文主要是介绍【学习笔记】CF930E Coins Exhibition，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

有没有更好的方法？

注意到，第三种转移加上第一种转移是将 $\le l_i$ 的 $D P$ 值推平成 $0$ ，那么我们维护一个指针 $p$ 表示 $[1, p]$ 这段前缀的 $D P$ 值都是 $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;
}