MnZn求问fhqtreap
  • 板块学术版
  • 楼主wangshi
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/25 10:56
  • 上次更新2023/11/3 01:21:20
查看原帖
MnZn求问fhqtreap
541553
wangshi楼主2023/8/25 10:56

日报中提到按排名分裂的fhqtreap可以这样查询排名

int findsiz(int now){
    int res=tree[now].siz-tree[tree[now].rs].siz;
    while(now!=root){//由于此种方式维护的父亲不保证根节点的父亲为空
        if(now==tree[tree[now].fa].rs)res+=(tree[tree[now].fa].siz-tree[now].siz);//如果当前点为父亲的右儿子,那么根据定义,其父亲及父亲的左子树的排都比当前点小,应被统计入答案,否则其父亲的排名大于当前点则不应统计
        now=tree[now].fa;//回溯
    }//跳出循环的条件为回溯到根节点即停,为何正确,因为每一个点统计的是自己为其父亲贡献的答案
    return res;//返回答案
}

但如果我进行了翻转操作,是否还能这样查询呢,蒟蒻自己实现的太随机了,有时候对有时候就错,,

2023/8/25 10:56
加载中...