萌新求助fhq treap

P3391 【模板】文艺平衡树

koishi_offical @ 2021-03-16 13:53:35

void split(int now,int siz,int &x,int &y)
  {
      if(!now)
        {
            x=y=0;
            return;
        }
        if(tr[now].rev) pushdown(now);
        if(tr[tr[now].l].siz<siz)
            {
                 x=now;
                 split(tr[now].r,siz-tr[tr[now].l].siz-1,tr[x].r,y);
            }
        else
            {
                 y=now;
                 split(tr[now].l,siz,x,tr[y].l);
            }
        update(now);
  }

如果把下放标记操作放到if和else里面

void split(int now,int siz,int &x,int &y)
  {
      if(!now)
        {
            x=y=0;
            return;
        }
        if(tr[tr[now].l].siz<siz)
            {
                if(tr[now].rev) pushdown(now);
                 x=now;
                 split(tr[now].r,siz-tr[tr[now].l].siz-1,tr[x].r,y);
            }
        else
            {
                if(tr[now].rev) pushdown(now);
                 y=now;
                 split(tr[now].l,siz,x,tr[y].l);
            }
        update(now);
  }

就会wa

这两个代码不应该是等价的吗


|