解释一下为何不用pushdown
查看原帖
解释一下为何不用pushdown
169594
Heart_Of_Iron_4楼主2025/1/22 09:59

这题线段树的目的是求解非0数字的个数。而cnt的意思是,每个点的权值为从这个点走到根节点路上cnt的和。
所以当一个节点cnt为0时,若 他的儿子 cnt也为0,显然不会在这个节点处对答案直接产生贡献,可能产生贡献(cnt!=0)的只可能是 他的儿子 的儿子,这表现在len上,所以累加len就行了。

更武断一点的版本:
如果一个区间整个都被加,那么len自然没儿子区间什么事;儿子区间cnt!=0时表示儿子区间单独被加,没大区间什么事,当大区间cnt=0时儿子区间一定还cnt!=0,这体现在len上,所以累加len就行。

可能说的不太清楚qaq

2025/1/22 09:59
加载中...