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 设置成本版本第一次修改完的根再修改也是错的。
求助如何正确实现。