线段树套有旋 Treap

luckydrawbox · 2023-08-03 08:32:03 · 个人记录

部分内容与 \text{Treap} 的相同，这里已省略，重点讲解线段树部分的功能。

另外，代码建树时需要一个辅助数组 b_i 代表第 i 个数的初始值。

宏定义

变量

函数

代码

int tot,nc[N*20];
int INF=2147483647;
struct Tree{
    int l,r,dat,sz,cnt;
    int val;
}a[N*20];
struct Treap{
    int rt;
    void pushup(int p){
        a[p].sz=a[a[p].l].sz+a[a[p].r].sz+a[p].cnt;
    }
    int get_new(int val){
        int p=nc[++tot];
        a[p].l=a[p].r=0;a[p].dat=rand();
        a[p].sz=a[p].cnt=1;a[p].val=val;
        return p;
    }
    void del(int &p){
        nc[tot--]=p;p=0;
    }
    void build(){
        rt=get_new(-INF);
        a[rt].r=get_new(INF);pushup(rt);
    }
    void zig(int &p){
        int q=a[p].l;
        a[p].l=a[q].r;a[q].r=p;p=q;
        pushup(a[p].r);pushup(p);
    }
    void zag(int &p){
        int q=a[p].r;
        a[p].r=a[q].l;a[q].l=p;p=q;
        pushup(a[p].l);pushup(p);
    }
    void insert(int &p,int val){
        if(!p){
            p=get_new(val);return;
        }
        if(a[p].val==val){
            a[p].cnt++;pushup(p);
            return;
        }
        if(val<a[p].val){
            insert(a[p].l,val);
            if(a[a[p].l].dat>a[p].dat)zig(p);
        }
        else{
            insert(a[p].r,val);
            if(a[a[p].r].dat>a[p].dat)zag(p);
        }
        pushup(p);
    }
    void remove(int &p,int val){
        if(!p)return;
        if(a[p].val==val){
            if(a[p].cnt>1){
                a[p].cnt--;pushup(p);
                return;
            }
            if(a[p].l||a[p].r){
                if(!a[p].r||a[a[p].l].dat>a[a[p].r].dat){
                    zig(p);remove(a[p].r,val);
                }
                else{
                    zag(p);remove(a[p].l,val);
                }
                pushup(p);return;
            }
            else del(p);
            return;
        }
        if(val<a[p].val)remove(a[p].l,val);
        else remove(a[p].r,val);
        pushup(p);
    }
    int VtoR(int p,int val){
        if(!p)return 0;
        if(val<a[p].val)return VtoR(a[p].l,val);
        if(val==a[p].val)return a[a[p].l].sz;
        return a[a[p].l].sz+a[p].cnt+VtoR(a[p].r,val);
    }
    int pre(int val){
        int ans=1,p=rt;
        while(p){
            if(val==a[p].val){
                if(a[p].l){
                    p=a[p].l;
                    while(a[p].r)p=a[p].r;
                    ans=p;
                }
                break;
            }
            if(a[p].val<val&&a[p].val>a[ans].val)
                ans=p;
            p=(val<a[p].val?a[p].l:a[p].r);
        }
        return a[ans].val;
    }
    int nxt(int val){
        int ans=2,p=rt;
        while(p){
            if(val==a[p].val){
                if(a[p].r){
                    p=a[p].r;
                    while(a[p].l)p=a[p].l;
                    ans=p;
                }
                break;
            }
            if(a[p].val>val&&a[p].val<a[ans].val)
                ans=p;
            p=(val<a[p].val?a[p].l:a[p].r);
        }
        return a[ans].val;
    }
    void dfs(int p){
        if(a[p].l)dfs(a[p].l);
        printf("(%d,%d) ",p,a[p].val);
        if(a[p].r)dfs(a[p].r);
    }
};
#define pl p<<1
#define pr p<<1|1
struct Segmet{
    Segmet(){
        srand(time(0));tot=0;
        for(int i=1;i<N*20;i++)nc[i]=i;
    }
    struct Tree{
        int l,r;
        Treap t;
    }s[N<<2];
    void build(int p,int l,int r){
        s[p].l=l;s[p].r=r;s[p].t.build();
        for(int i=l;i<=r;i++)
            s[p].t.insert(s[p].t.rt,b[i]);
        if(l==r)return;
        int mid=(l+r)>>1;
        build(pl,l,mid);build(pr,mid+1,r);
    }
    void change(int p,int x,int lv,int nv){
        s[p].t.remove(s[p].t.rt,lv);
        s[p].t.insert(s[p].t.rt,nv);
        if(s[p].l==s[p].r)return;
        int mid=(s[p].l+s[p].r)>>1;
        if(x<=mid)change(pl,x,lv,nv);
        else change(pr,x,lv,nv);
    }
    int VtoR(int p,int l,int r,int val){
        if(l<=s[p].l&&s[p].r<=r){
            return s[p].t.VtoR(s[p].t.rt,val)-1;
        }
        int mid=(s[p].l+s[p].r)>>1;
        int ans=0;
        if(l<=mid)ans+=VtoR(pl,l,r,val);
        if(r>mid)ans+=VtoR(pr,l,r,val);
        return ans;
    }
    int RtoV(int l,int r,int rank){
        ll L=0,R=1e8;
        while(L<R){
            ll mid=(L+R+1)>>1;
            if(VtoR(1,l,r,mid)+1<=rank)L=mid;
            else R=mid-1;
        }
        return L;
    }
    int pre(int p,int l,int r,int val){
        if(l<=s[p].l&&s[p].r<=r)
            return s[p].t.pre(val);
        int mid=(s[p].l+s[p].r)>>1;
        int ans=-INF;
        if(l<=mid)ans=max(ans,pre(pl,l,r,val));
        if(r>mid)ans=max(ans,pre(pr,l,r,val));
        return ans;
    }
    int nxt(int p,int l,int r,int val){
        if(l<=s[p].l&&s[p].r<=r)
            return s[p].t.nxt(val);
        int mid=(s[p].l+s[p].r)>>1;
        int ans=INF;
        if(l<=mid)ans=min(ans,nxt(pl,l,r,val));
        if(r>mid)ans=min(ans,nxt(pr,l,r,val));
        return ans;
    }
}tree;