Solution-P8582

CaiZi · 2025-04-05 16:30:19 · 题解

首先序列长度不是 2 的次幂非常难受，考虑把它补成 2 的次幂，多余的位置 s_i=1。然后考虑把这些东西插入 01-trie。以下记 dep_i 为节点 i 距离最近叶子节点的距离（不是传统的定义），那么点 i 的子树的叶子个数为 2^{dep_i}，若点 i 这一位为 1，则贡献为 2^{dep_i-1}。

然后我们要知道，01-trie 和线段树是等价的。对于点 i 的子树的叶子，其在从高往低数前 i 位是相同的，这启发我们在线段树上将其拆成 \log n 个长度为 2^l 的区间处理，然后分别处理。

我们先考虑从点 1 到点 i 这一段拼接而成的数的最小贡献，直接在 01-trie 上贪心，能走数字相同的点就走，否则若当前在点 j，会有 2^{dep_i}\times2^{dep_j-1} 的贡献（前面为贡献的点的个数，后面为单个点贡献的值）。

我们再考虑点 i 的子树的最小贡献，首先高位尽量相同肯定是更优的，因此不能破坏前一步走的路径，设当前在点 j，我们本质上要求的就是点 j 的子树的最小贡献，设为 val_j，考虑标记合并。记 lc,rc 分别为左右儿子。

• 如果左右子树都可以走，则左右子树中的叶子均没有任何贡献，val_j 为 val_{lc}+val_{rc}。
• 如果只有左子树可以走，因为右子树除了右儿子以外的其他部分和左子树是一样的，同时右子树的所有叶子都需要额外加上右儿子的贡献，val_j 为 2val_{lc}+2^{dep_j-1}\times2^{dep_j-1}。只有右子树可以走的情况同理。
• 否则，val_j 为 -1，表示点 j 的子树不可以走。

修改操作直接上线段树打懒标记，如果点 i 对应的区间全被修改为 0，val_i 改为 -1，否则 val_i 改为 0。

时间复杂度 O(n\log n+m\log^2n)。

01-trie 的题直接讲都非常抽象，建议配合代码理解。代码展示：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int v,n,m,k,dep[524288],val[524288],tag[524288];
inline void pushup(int p){
    if(val[p<<1]!=-1&&val[p<<1|1]!=-1){
        val[p]=val[p<<1]+val[p<<1|1];
    }
    else if(val[p<<1]!=-1){
        val[p]=(val[p<<1]<<1)+((int)(1)<<(dep[p]<<1)-2);
    }
    else if(val[p<<1|1]!=-1){
        val[p]=(val[p<<1|1]<<1)+((int)(1)<<(dep[p]<<1)-2);
    }
    else{
        val[p]=-1;
    }
}
inline void pushdown(int p){
    if(tag[p]!=-1){
        if(tag[p]){
            val[p<<1]=val[p<<1|1]=0;
        }
        else{
            val[p<<1]=val[p<<1|1]=-1;
        }
        tag[p<<1]=tag[p<<1|1]=tag[p];
        tag[p]=-1;
    }
}
inline void build(int l,int r,int p,int t){
    tag[p]=-1;
    dep[p]=t;
    if(l==r){
        if(l>n){
            val[p]=-1;
        }
        return;
    }
    build(l,l+r>>1,p<<1,t-1);
    build((l+r>>1)+1,r,p<<1|1,t-1);
    pushup(p);
}
inline void update(int l,int r,int p,int a,int b,int c){
    if(a<=l&&r<=b){
        tag[p]=c;
        if(c){
            val[p]=0;
        }
        else{
            val[p]=-1;
        }
        return;
    }
    pushdown(p);
    if(a<=(l+r>>1)){
        update(l,l+r>>1,p<<1,a,b,c);
    }
    if(b>(l+r>>1)){
        update((l+r>>1)+1,r,p<<1|1,a,b,c);
    }
    pushup(p);
}
inline int find(int p,int t,int s){
    if(dep[p]==t){
        return val[p];
    }
    pushdown(p);
    if(val[(p<<1)|(s>>dep[p]-1&1)]!=-1){
        return find((p<<1)|(s>>dep[p]-1&1),t,s);
    }
    else{
        return find((p<<1)|(s>>dep[p]-1&1^1),t,s)+((int)(1)<<dep[p]+t-1);
    }
}
inline int query(int l,int r,int p,int a,int b,int s){
    if(a<=l&&r<=b){
        return find(1,dep[p],s);
    }
    int c=0;
    pushdown(p);
    if(a<=(l+r>>1)){
        c+=query(l,l+r>>1,p<<1,a,b,s);
    }
    if(b>(l+r>>1)){
        c+=query((l+r>>1)+1,r,p<<1|1,a,b,s+(1<<dep[p]-1));
    }
    return c;
}
signed main(){
    int p,a,b;
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>v>>m>>n;
    for(;(1<<k)<=n;k++);
    build(0,(1<<k)-1,1,k);
    while(v--){
        cin>>a>>b;
        update(0,(1<<k)-1,1,a,b,0);
    }
    while(m--){
        cin>>p>>a>>b;
        if(p==0){
            if(val[1]==-1){
                cout<<"Death\n";
            }
            else{
                cout<<query(0,(1<<k)-1,1,a,b,0)<<'\n';
            }
        }
        else{
            update(0,(1<<k)-1,1,a,b,p-1);
        }
    }
    return 0;
}