首页 > 其他分享 >非旋treap

非旋treap

时间：2023-03-16 09:58:52浏览次数：33  
标签：rt val int treap 非旋 il cs ri

非旋treap

基本操作

简述

\(FHQ\) \(treap\)借用了\(treap\)的特点，基于\(split\)和\(merge\)操作实现，因其不用旋转，又叫非旋\(treap\)，优点是好理解，上手快，代码短 （ps: 重点是好写）

#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]

struct tree{
    int sz,val,pri,ch[2];
}t[N<<2];

il int add(cs int val){
    t[++cnt].sz=1;
    t[cnt].val=val;
    t[cnt].pri=srd();
    return cnt;
}

il void upd(cs int rt){
    t[rt].sz=1+t[ls(rt)].sz+t[rs(rt)].sz;
}

分裂

这里是按照权值分裂，小于等于\(k\)的在左边（\(x\)），大于的在右边（\(y\)），也可以按子树大小分

il void split(cs int rt,cs int k,int &x,int &y){

    if(!rt) x=y=0;
    else{
        if(t[rt].val<=k) x=rt,split(rs(rt),k,rs(x),y);
        else y=rt,split(ls(rt),k,x,ls(y));
        t[rt].sz=1+t[ls(rt)].sz+t[rs(rt)].sz;//
    }
    return;
}

合并

要保证\(x\)的权值（子树大小）比\(y\)的小，具体看分裂按什么分

il int merge(cs int x,cs int y){ //val[x]<val[y]
    if(!x||!y) return x+y;
    if(t[x].pri<t[y].pri){
        rs(x)=merge(rs(x),y);
        t[x].sz=1+t[ls(x)].sz+t[rs(x)].sz;
        return x;
    } 
    else{
        ls(y)=merge(x,ls(y));
        t[y].sz=1+t[ls(y)].sz+t[rs(y)].sz;
        return y;
    }
}

\(insert\)

to be continue~

il void ins(int &rt,cs int val){
    ri int x,y;
    split(rt,val,x,y);
    rt=merge(merge(x,add(val)),y);
    return;
}

\(delete\)

to be continue~

il void del(int &rt,cs int val){
    ri int x,y,z;
    split(rt,val,x,z),split(x,val-1,x,y);
    y=merge(ls(y),rs(y));
    rt=merge(merge(x,y),z);
    return;
}

查询\(k\)的排名

to be continue~

il int rnk(int &rt,cs int val){
    ri int x,y,as;
    split(rt,val-1,x,y);
    as=t[x].sz+1,rt=merge(x,y);
    return as;
}

查询排名为\(k\)的数

to be continue~

il int kth(cs int rt,int k){
    ri int o=rt;
    while(1){//rt=0
        if(k<=t[ls(o)].sz) o=ls(o);
        else if(k==t[ls(o)].sz+1) return o;//
        else k-=t[ls(o)].sz+1,o=rs(o);//
    }
}

查询\(k\)的前驱

to be continue~

il int pre(int &rt,cs int val){
    ri int x,y,as;
    split(rt,val-1,x,y);
    as=t[kth(x,t[x].sz)].val;
    rt=merge(x,y);
    return as;
}

查询\(k\)的后继

to be continue~

il int nxt(int &rt,cs int val){
    ri int x,y,as;
    split(rt,val,x,y);
    as=t[kth(y,1)].val;
    rt=merge(x,y);
    return as;
}
AC·code 
#include <bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define F(s) freopen(#s".in","r",stdin),freopen(#s".out","w",stdout);            
using namespace std;

namespace Q{
    il int rd(){
        ri int x=0;ri bool f=0;ri char c=getchar();
        while(!isdigit(c)) f|=(c==45),c=getchar();
        while(isdigit(c)) x=x*10+(c^48),c=getchar();
        return f?-x:x;
    }
    il void wt(int x){
        if(x<0) x=-x,putchar(45);
        if(x>=10) wt(x/10);
        return putchar(x%10|48),void();
    }
    il void wn(int x,char c=10){
        wt(x),putchar(c);
    }
} using namespace Q;

cs int N=1e5+5;
int cnt,rot,n;
mt19937 srd(time(0));

namespace fhq_treap{
    #define ls(x) t[x].ch[0]
    #define rs(x) t[x].ch[1]

    struct tree{
        int sz,val,pri,ch[2];
    }t[N<<2];

    il int add(cs int val){
        t[++cnt].sz=1;
        t[cnt].val=val;
        t[cnt].pri=srd();
        return cnt;
    }

    il void split(cs int rt,cs int k,int &x,int &y){
        if(!rt) x=y=0;
        else{
            if(t[rt].val<=k) x=rt,split(rs(rt),k,rs(x),y);
            else y=rt,split(ls(rt),k,x,ls(y));
            t[rt].sz=1+t[ls(rt)].sz+t[rs(rt)].sz;//
        }
        return;
    }

    il int merge(cs int x,cs int y){
        if(!x||!y) return x+y;
        if(t[x].pri<t[y].pri){
            rs(x)=merge(rs(x),y);
            t[x].sz=1+t[ls(x)].sz+t[rs(x)].sz;
            return x;
        } 
        else{
            ls(y)=merge(x,ls(y));
            t[y].sz=1+t[ls(y)].sz+t[rs(y)].sz;
            return y;
        }
    }

    il void del(int &rt,cs int val){
        ri int x,y,z;
        split(rt,val,x,z),split(x,val-1,x,y);
        y=merge(ls(y),rs(y));
        rt=merge(merge(x,y),z);
        return;
    }

    il void ins(int &rt,cs int val){
        ri int x,y;
        split(rt,val,x,y);
        rt=merge(merge(x,add(val)),y);
        return;
    }

    il int rnk(int &rt,cs int val){
        ri int x,y,as;
        split(rt,val-1,x,y);
        as=t[x].sz+1,rt=merge(x,y);
        return as;
    }

    il int kth(cs int rt,int k){
        ri int o=rt;
        while(1){//rt=0
            if(k<=t[ls(o)].sz) o=ls(o);
            else if(k==t[ls(o)].sz+1) return o;//
            else k-=t[ls(o)].sz+1,o=rs(o);//
        }
    }

    il int pre(int &rt,cs int val){
        ri int x,y,as;
        split(rt,val-1,x,y);
        as=t[kth(x,t[x].sz)].val;
        rt=merge(x,y);
        return as;
    }

    il int nxt(int &rt,cs int val){
        ri int x,y,as;
        split(rt,val,x,y);
        as=t[kth(y,1)].val;
        rt=merge(x,y);
        return as;
    }
} using namespace fhq_treap;

signed main(){
    n=rd();
    for(ri int i=1,op,x;i<=n;++i){
        op=rd(),x=rd();
        switch (op){
            case 1: ins(rot,x); break;
            case 2: del(rot,x); break;
            case 3: wn(rnk(rot,x)); break;
            case 4: wn(t[kth(rot,x)].val); break;
            case 5: wn(pre(rot,x)); break;
            default: wn(nxt(rot,x));break;
        }
    }
    return 0;
}

区间翻转

把 \([l, r]\) 分裂出来（按子树大小），打上懒标记，再合并回去，记得下放懒标记

il void rev(int &rt,int l,int r){
    ri int x,y,z;
    split(rt,r,x,z),split(x,l-1,x,y);
    t[y].lz^=1,rt=merge(merge(x,y),z);
}

\(split\)有一点差异

il void split(cs int rt,cs int k,int &x,int &y){
    if(!rt) x=y=0;
    else{
        pushdown(rt);
        if(t[ls(rt)].sz<k){ //要减去左儿子的size!
            x=rt,split(rs(rt),k-t[ls(rt)].sz-1,rs(x),y);
        }
        else y=rt,split(ls(rt),k,x,ls(y));
        t[rt].sz=1+t[ls(rt)].sz+t[rs(rt)].sz;//
    }
    return;
}

\(merge\) 要在合并前下放标记

il int merge(cs int x,cs int y){//sz[x]<sz[y]
    if(!x||!y) return x+y;
    if(t[x].pri<t[y].pri){
        pushdown(x);
        rs(x)=merge(rs(x),y);
        t[x].sz=1+t[ls(x)].sz+t[rs(x)].sz;
        return x;
    } 
    else{
        pushdown(y);
        ls(y)=merge(x,ls(y));
        t[y].sz=1+t[ls(y)].sz+t[rs(y)].sz;
        return y;
    }
}
AC·code 
#include <bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define F(s) freopen(#s".in","r",stdin),freopen(#s".out","w",stdout);            
using namespace std;

namespace Q{
    il int rd(){
        ri int x=0;ri bool f=0;ri char c=getchar();
        while(!isdigit(c)) f|=(c==45),c=getchar();
        while(isdigit(c)) x=x*10+(c^48),c=getchar();
        return f?-x:x;
    }
    il void wt(int x){
        if(x<0) x=-x,putchar(45);
        if(x>=10) wt(x/10);
        return putchar(x%10|48),void();
    }
} using namespace Q;

cs int N=1e5+5;
int cnt,rot,n,m;
mt19937 srd(time(0));

namespace fhq_treap{
    #define ls(x) t[x].ch[0]
    #define rs(x) t[x].ch[1]

    struct tree{
        int sz,val,pri,ch[2],lz;
    }t[N<<2];

    il void pushdown(int rt){
        if(t[rt].lz){
            t[rt].lz=0;
            swap(ls(rt),rs(rt));
            t[ls(rt)].lz^=1;
            t[rs(rt)].lz^=1;
        }
    }

    il int add(cs int val){
        t[++cnt].sz=1;
        t[cnt].val=val;
        t[cnt].pri=srd();
        return cnt;
    }

    il void split(cs int rt,cs int k,int &x,int &y){
        if(!rt) x=y=0;
        else{
            pushdown(rt);
            if(t[ls(rt)].sz<k){
                x=rt,split(rs(rt),k-t[ls(rt)].sz-1,rs(x),y);
            }
            else y=rt,split(ls(rt),k,x,ls(y));
            t[rt].sz=1+t[ls(rt)].sz+t[rs(rt)].sz;//
        }
        return;
    }

    il int merge(cs int x,cs int y){//sz[x]<sz[y]
        if(!x||!y) return x+y;
        if(t[x].pri<t[y].pri){
            pushdown(x);
            rs(x)=merge(rs(x),y);
            t[x].sz=1+t[ls(x)].sz+t[rs(x)].sz;
            return x;
        } 
        else{
            pushdown(y);
            ls(y)=merge(x,ls(y));
            t[y].sz=1+t[ls(y)].sz+t[rs(y)].sz;
            return y;
        }
    }

    il void rev(int &rt,int l,int r){
        ri int x,y,z;
        split(rt,r,x,z),split(x,l-1,x,y);
        t[y].lz^=1,rt=merge(merge(x,y),z);
    }

    il void prt(int rt){
        pushdown(rt);
        if(ls(rt)) prt(ls(rt));
        wt(t[rt].val),putchar(32);
        if(rs(rt)) prt(rs(rt));
    }
} using namespace fhq_treap;

signed main(){
    n=rd(),m=rd();
    for(ri int i=1;i<=n;++i){
        rot=merge(rot,add(i));
    } 
    for(ri int i=1,l,r;i<=m;++i){
        l=rd(),r=rd(),rev(rot,l,r);
    } 
    prt(rot);
    return 0;
}

标签：rt,val,int,treap,非旋,il,cs,ri
From： https://www.cnblogs.com/windymoon/p/17221179.html

相关文章

  • treap
    \(treap\)基本操作简述\(treap\)将二叉搜索树和堆结合在一起为维护深度，给每个节点随机分配权值\(dat\)，如下structtree{ints[2],vl,dt,ct,sz;}t[N];ilvoidupd(cs......
  • 【学习笔记】FHQ Treap
    \(\textbf{I.基本操作}\)\(\textbf{维护子树大小/size_up()}\)和线段树中的\(\text{push_up}\)操作类似，目的是维护以一个节点为根的子树的节点个数。inlinevoids......
  • FHQ-Treap 学习笔记
    FHQ-Treap学习笔记Treap=Tree+Heap.Treap是一种弱平衡二叉树，可以看作是笛卡尔树：其每个点有一个二元组\((Key,Value)\)，\(Key\)满足二叉搜索树的性质，而\(Value\)......
  • fhq_treap
    FHQtreap参考:链接Treap:优点:码量小好写核心代码是复读机好理解支持操作多缺点:常数大了点维护平衡的奇怪操作:Treap:旋转FHQTreap:分裂合并节点信......
  • BZOJ 3224 普通平衡树 （BST+Treap）
    题目描述：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：插入数值x。删除数值x(若有多个相同的数，应只删除一个)。查询数值x的排名(若有多个相同的数，应......
  • Treap 平衡二叉查找树
    【基本概念】Treap=Tree+Heap。Tree是指二叉搜索树，而Heap指的是二叉堆，一般是最小堆。Treap需要维护两值，一个是二叉搜索树中的键值（key），另一个是最小堆中的优先级（aux）。Treap是......
  • POJ2761 Feed the dogs（Treap）
    DescriptionWindlovesprettydogsverymuch,andshehasnpetdogs.SoJiajiahastofeedthedogseverydayforWind.JiajialovesWind,butnotthedogs,......
  • BZOJ1503 郁闷的出纳员 （Treap）
    DescriptionOIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们......
  • 学习笔记：二叉平衡树之 fhp-treap
    问题背景：你需要维护一个整数集合，可以满足一下几种操作：插入一个整数xx。删除一个整数xx（若有多个相同的数，只删除一个）。查询整数xx的排名（排名定义为比当前数小......
  • FHQ-treap 学习笔记
    FHQ-Treap学习这种平衡树不需要了解treap，据说treap和splay能干的事情他也能干。update：2023.1.12以前写的博客看起来太仓促了，修改了一下。前置芝士二叉搜索树的性......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99