给警钟一拳(,如果你RE #1236但是讨论区指出的问题你都没有
查看原帖
给警钟一拳(,如果你RE #1236但是讨论区指出的问题你都没有
177000
vicky2048_2楼主2023/11/13 15:01

这种错法应该是比较少有人错的(

如果你写主席树习惯在插入函数传入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);//回收结点时不要再把pre传成lc/rc[no]了(
    }

这是这题合并两棵树之后对小树结点对应的历史版本线段树进行修改,此时将child作为pre传入显然是错的(

讨论区不用注意markdown格式好爽

2023/11/13 15:01
加载中...