关于可持久化平衡树合并的困惑

P3835 【模板】可持久化平衡树

@[hh弟中弟](/user/366639) 可能是合并的时候用的点,要么是分裂的时候分裂出来的新建点,要么是插入的新点,不会影响到原树,我是这么理解的,所以当你合并的时候不再全是split中新建的点就会出错,貌似这道题由于插入删除的性质,你分裂出来的两部分都是值域紧挨着待修改位置的,所以合并只会合并新建的点
by yizhiming @ 2024-01-10 16:24:47


我测试了一下其他可持久化平衡树题[Link](https://www.luogu.com.cn/record/142427883),这个题由于可持久化是用来维护复制区间,合并的时候不新建就暴毙了
by yizhiming @ 2024-01-10 16:27:05


@[yizhiming](/user/369399) 你分裂出来的两部分都是值域紧挨着待修改位置的 为什么这样就能只合并新建的点
by hh弟中弟 @ 2024-01-10 16:37:33


@[yizhiming](/user/369399) 有一篇[博客](https://www.cnblogs.com/chy-2003/p/11825302.html)好像说了这个问题,我拍了一下,确实很快拍出错了
by hh弟中弟 @ 2024-01-10 16:39:16


@[hh弟中弟](/user/366639) 哦谢谢,看来我只理解对了一半,数据还是太水了(((
by yizhiming @ 2024-01-10 16:43:03


哦也不是,和我想得差不多,但我忽略了相同权值不会合并成一个点的情况。
by yizhiming @ 2024-01-10 16:44:13


@[yizhiming](/user/369399) 你分裂出来的两部分都是值域紧挨着待修改位置的,这样只能说明大概率合并新建的点吧
by hh弟中弟 @ 2024-01-10 16:44:18


@[hh弟中弟](/user/366639) 是这样的
by yizhiming @ 2024-01-10 16:44:52


|