求助Splay RE
  • 板块学术版
  • 楼主2020kanade
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/16 18:28
  • 上次更新2023/10/28 06:26:59
查看原帖
求助Splay RE
456724
2020kanade楼主2022/3/16 18:28

闲的没事玩玩自己以前写的Splay,结果发现会被某些数据整RE掉?

核心代码(由于整个太长,仅给出结点定义,旋转,splay操作,插入删除以及其依赖的函数):

typedef long long LL;
struct node
{
    node *ch[2],*fa;LL v,c,sz;//权值,当前值个数,子树(包含自身)大小
    inline node(LL v):v(v) {ch[0]=ch[1]=fa=nullptr;c=sz=rsz=1;}
    inline void up() {sz=0,rsz=1;if(ch[0]) sz+=ch[0]->sz,rsz+=ch[0]->rsz;if(ch[1]) sz+=ch[1]->sz,rsz+=ch[1]->rsz;sz+=c;}
    inline LL getf() {if(!fa) return -1;return this==fa->ch[1];}//其实是获取当前结点是左还是右儿子,还是没爹
    inline void set_ch(node* &t,LL k) {if(!t) {ch[k]=nullptr;up();return;}ch[k]=t,t->fa=this;up();}
    inline ~node() {if(ch[0]) delete ch[0];if(ch[1]) delete ch[1];ch[0]=ch[1]=nullptr;}
};
inline LL siz(node* rs) {return rs?rs->sz:0;}//获取当前点大小

inline void rotate(node* &rs)
{
    if(!rs||!rs->fa) return;node *f=rs->fa,*ff=nullptr;ff=f->fa;LL chk=rs->getf();
    f->set_ch(rs->ch[chk^1],chk);rs->set_ch(f,chk^1);rs->fa=ff;
    if(ff) ff->ch[ff->ch[1]==f]=rs,ff->up();
}//将rs向上旋转一层

inline void splay(node* &rs,node *t,node* &rt)
{
    if(!rs) return;
    for(;rs->fa!=t;rotate(rs)) if(rs->fa && rs->fa->fa!=t) rs->fa->getf()==rs->getf()?rotate(rs->fa):rotate(rs);if(!t) rt=rs;
}//将rs旋转至t下面,根为rt
inline void insert(node* &rt,LL v)
{
    node *ne=new node(v),*rs=rt,*lst=rs?rs->fa:nullptr;
    while(rs)
    {
        lst=rs;if(rs->v==ne->v) {delete ne;rs->c++,rs->sz++;splay(rs,nullptr,rt);return;}
        if(ne->v<rs->v) rs=rs->ch[0];else rs=rs->ch[1];
    }
    if(!lst) rt=ne;else {if(ne->v<lst->v) lst->set_ch(ne,0);else lst->set_ch(ne,1);splay(ne,nullptr,rt);}
}//在以rt为根的树中插入一个权值为v的点(有相同的会合并为一个点)
inline node* nf(node* &rt,LL v)
{
    node *rs=rt,*lst=nullptr;while(rs) {lst=rs;if(rs->v==v) break;if(v<rs->v) rs=rs->ch[0];else rs=rs->ch[1];}
    if(rs) splay(rs,nullptr,rt);else splay(lst,nullptr,rt);return rs;
}//查找以rt为根的树中权值为v的点的地址(未找到返回nullptr)
inline bool del(node* &rt,LL v)
{
    node* rs=nf(rt,v);if(!rs) return 0;
    if(rs->c>1) {rs->c-=1,rs->sz-=1;if(rs->fa) rs->fa->up();return 1;}
    if(!rs->ch[0] && !rs->ch[1]) rt=nullptr;
    else if(!rs->ch[0]) rs->ch[1]->fa=nullptr,rt=rs->ch[1];else if(!rs->ch[1]) rs->ch[0]->fa=nullptr,rt=rs->ch[0];
    else{
        node *res=rs->ch[0];while(res->ch[1]) res=res->ch[1];splay(res,rs,rt);
        res->set_ch(rs->ch[1],1);res->fa=nullptr;rt=res;
    }
    delete rs,rs=nullptr;return 1;
}//在以rt为根的树中删除权值为v的点,存在多个仅删除一个,返回删除结果

以下的数据每行第一个数字1为插入,2为删除,第二个数字代表所插入/删除的值,则下面这组数据

1 1
1 2
2 2
2 1

会直接造成RE。(类似的应该也可以)

目前已探明RE发生在最后删除时调用的nf函数进行的splay过程中,但是具体原因以及措施仍未查明。

请求各位神犇施以援手,本人不胜感激

2022/3/16 18:28
加载中...