这种错法应该是比较少有人错的(
如果你写主席树习惯在插入函数传入pre时将child[x]传为pre,那么在写在旧节点更新时你大概会因为这个陋习而误将child[x]传为pre
也就是说
inline void ins(int &no,int pre,int l,int r,int pl){
if(l>pl||r<pl) return ;
no=++bh,lc[no]=lc[pre],rc[no]=rc[pre],num[no]=num[pre]+1;
if(l==r) return ;
int mi=l+r>>1;
ins(L,L,l,mi,pl),ins(R,R,mi+1,r,pl);
}
上面是主席树板子里的单点修改函数,这里是在边修改边建历史版本线段树,所以直接将lc/rc[x]传为pre显然是正确的(
inline void add(int no,int pre,int l,int r,int pl){
num[no]=num[pre]+1;
if(l==r) return ;
int mi=l+r>>1;
if(pl>=mi+1) lc[no]=lc[pre],add(R,rc[pre],mi+1,r,pl);
else rc[no]=rc[pre],add(L,lc[pre],l,mi,pl);
}
这是这题合并两棵树之后对小树结点对应的历史版本线段树进行修改,此时将child作为pre传入显然是错的(
讨论区不用注意markdown格式好爽