主席树如何在同一版本上多次修改
  • 板块学术版
  • 楼主Subset_Sum
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/28 13:26
  • 上次更新2023/11/2 17:44:48
查看原帖
主席树如何在同一版本上多次修改
528981
Subset_Sum楼主2023/9/28 13:26

RT,好几次写主席树遇到这个问题了,要么就是调半天,要么就是版本太多 TLE 了。

比如可持久化 dsu,我在一个下标上同时存了 father 和 dep 两个信息。我合并 dsu 的时候需要新建一个版本,分别修改两个不同位置的 father 和 dep,但是我发现用我的主席树板子:

if(d<=mid){
   insert(ls[p],ls[las],l,mid,d,x,op);
   rs[p]=rs[las];
}
else{
   insert(rs[p],rs[las],mid+1,r,d,x,op);
   ls[p]=ls[las];
}

如果我想做同版本多次修改的话,那么我在第一次插入时维护好的 rs 和 ls 可能会在第二次被还原掉。

我尝试了一下判断左右儿子是否为空再赋值,但是也是错的(昨天晚上发现的,错因已经忘了)。刚刚试了试第二次修改时把 las 设置成本版本第一次修改完的根再修改也是错的。

求助如何正确实现。

2023/9/28 13:26
加载中...