自动搬运

查看原文

来自洛谷，原作者为

	CaiZi 初三蒟蒻 || 坐标 FJ || ENFP-A || MC&PVZ&RS 玩家 || 出题团为 CZOI（80765）

搬运于2025-08-24 22:40:23，当前版本为作者最后更新于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;
}