【学习笔记】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\lt j\lt 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;
}