有关此题的线段树合并做法

P3899 [湖南集训] 更为厉害

有一篇题解解释说: > 但是x线段树递归到某个空子树的时候,还是要把y上对应的子树拿过来,这可以相当于是打标记,暂时用了y的子树。正经合并的时候肯定是不能改变y的信息了。 但我不明白这哪里打标记了。。。
by Alan_Zhao @ 2021-06-27 19:56:54


父节点在合并之后不是就不会再更改了吗
by 南门阳德 @ 2021-06-27 20:01:09


@[南门阳德](/user/178111) 也有题解把更改放在合并后面,也能过
by Alan_Zhao @ 2021-06-27 20:05:35


@[Alan_Zhao](/user/225625) 如果每颗线段树都完全独立的话时空复杂度是不可能对的。
by linfourxu @ 2021-06-27 20:07:57


如果其他儿子再向这里合并不就新开节点了吗
by 南门阳德 @ 2021-06-27 20:09:01


或者再更改
by 南门阳德 @ 2021-06-27 20:09:38


只有在不影响儿子的前提下才会直接使用儿子的节点啊。
by 南门阳德 @ 2021-06-27 20:10:21


@[Alan_Zhao](/user/225625) 当一个节点已经跟他父亲合并时,他的使命就已经结束了,有关他的询问就已经处理好了。
by linfourxu @ 2021-06-27 20:10:23


@[linfourxu](/user/50477) 好像不是的,题解里全是在线做法
by Alan_Zhao @ 2021-06-27 20:12:29


@[linfourxu](/user/50477) 这个倒不太正确吧,毕竟这个题不能直接存答案,必须在线段树上差。
by 南门阳德 @ 2021-06-27 20:13:18


| 下一页