无旋treap-fhqtreap

GBLoi · 2020-04-22 16:36:13 · 个人记录

Think Functional !    
                                              ---------------> fhq

可以先了解一下fhq大佬和他的ppt

• https://user.guancha.cn/main/content?id=139582&page=0
• https://wenku.baidu.com/view/a5f6fefe0066f5335a8121fa.html

贴上7位dalao的blog(关于fhqtreap)

• https://www.luogu.com.cn/blog/Chanis/fhq-treap
• https://blog.sengxian.com/algorithms/treap
• https://www.cnblogs.com/Juruo1103/p/10281403.html#autoid-0-0-0
• https://blog.csdn.net/weixin_33738578/article/details/94484750?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-7&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-7
• https://blog.csdn.net/CABI_ZGX/article/details/79963427
• https://www.cnblogs.com/zzctommy/p/12416190.html
• https://www.luogu.com.cn/blog/zhy123456/fhq-treap

说明：本blog split 是按<= 和 > 分裂，merge 按大根堆合并

按值分裂

适用于维护大小关系的题目。

这是luogu的一道模板题

@！（……&……）

数组版

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
struct node
{
    int val;
    int pri;
    int size;
    int lc,rc;
    #define v(x) t[x].val
    #define p(x) t[x].pri
    #define s(x) t[x].size
    #define lc(x) t[x].lc
    #define rc(x) t[x].rc
}t[2*N];
int root=0,cnt=0;
inline void update(const int &now)
{
    s(now)=s(lc(now))+s(rc(now))+1;
    return;
}
inline int newnode(const int &val)
{
    cnt++;
    v(cnt)=val;
    p(cnt)=rand();
    s(cnt)=1;
    lc(cnt)=0;
    rc(cnt)=0;
    return cnt;
}
int merge(int x,int y) //x<=y
{
    if(x==0||y==0)  
        return x+y;
    if(p(x)>p(y)) {
        rc(x)=merge(rc(x),y);
        update(x);
        return x;
    }
    else {
        lc(y)=merge(x,lc(y));
        update(y);
        return y;
    }
}
void split(int now,const int &key,int &x,int &y) //x<=key,y>key
{
    if(now==0) {
        x=y=0;  
        return;
    }
    if(v(now)<=key) {
        x=now;
        split(rc(x),key,rc(x),y);
        update(x);
        return;
    }
    else {
        y=now;
        split(lc(y),key,x,lc(y));
        update(y);
        return;
    }
    return;
}
inline void insert(const int &key)
{
    int x,y,z;
    split(root,key,x,y);
    root=merge(merge(x,newnode(key)),y);
    return;
}
inline void erase(const int &key)
{
    int x,y,z;
    split(root,key,x,z);
    split(x,key-1,x,y);
    y=merge(lc(y),rc(y));
    x=merge(x,y);
    root=merge(x,z);
    return;
}
inline int getpre(const int &key)
{
    int x,y,z;
    split(root,key-1,x,y);
    int now=x;
    while(rc(now)) 
        now=rc(now);
    root=merge(x,y);
    return v(now);
}
inline int getsuf(const int &key)
{
    int x,y,z;
    split(root,key,x,y);
    int now=y;
    while(lc(now)) 
        now=lc(now);
    root=merge(x,y);
    return v(now);
}
inline int getrank(const int &key)
{
    int x,y,z;
    split(root,key-1,x,y);
    int tmp=s(x)+1;
    root=merge(x,y);
    return tmp;
}
inline int getnum(int rank)
{
    int now=root;
    while(rank>0&&now>0) {
        if(s(lc(now))+1==rank) 
            return v(now);
        if(s(lc(now))+1>rank) 
            now=lc(now);
        else rank-=s(lc(now))+1,now=rc(now);
    }
    return v(now);
}
/*
插入 xx 数
删除 xx 数(若有多个相同的数，因只删除一个)
查询 xx 数的排名(排名定义为比当前数小的数的个数 +1 )
查询排名为 xx 的数
求 xx 的前驱(前驱定义为小于 xx，且最大的数)
求 xx 的后继(后继定义为大于 xx，且最小的数)
*/
int main()
{
//  freopen("1.in","r",stdin);
    srand((unsigned)time(0));
    int n;
    scanf("%d",&n);
    int opt,x;
    while(n--) {
        scanf("%d%d",&opt,&x);
        switch(opt) {
            case 1 : insert(x); break;
            case 2 : erase(x); break;
            case 3 : printf("%d\n",getrank(x)); break;
            case 4 : printf("%d\n",getnum(x)); break;
            case 5 : printf("%d\n",getpre(x)); break; 
            case 6 : printf("%d\n",getsuf(x)); break;
        }   
    }
    return 0;
}

指针版（会快一点，但是谨慎食用）

#include<bits/stdc++.h>
using namespace std;
#define siz(x) ((x==NULL) ? 0 : x->size)
struct node
{
    int val;
    int size;
    int pri;
    node *lc,*rc;
    void update()
    {
        size=siz(lc)+siz(rc)+1;
        return;
    }
};
node *root = NULL;
node* newnode(const int &key)
{
    node *now;
    now = new node;
    now->val = key;
    now->pri = rand();
    now->lc = NULL;
    now->rc = NULL;
    now->size = 1;
    return now;
}
void split(node *now,const int &key,node *&x,node *&y)
{
    if(now==NULL) {
        x = y = NULL;
        return;
    }
    if(now->val <= key) {
        x = now;
        split(now->rc,key,x->rc,y);
        x->update();
    }
    else {
        y = now;
        split(now->lc,key,x,y->lc);
        y->update();
    }
    return;
}
node* merge(node *x,node *y)
{
    if(x==NULL) return y;
    if(y==NULL) return x;
    if(x->pri > y->pri) {
        x->rc = merge(x->rc,y);
        x->update();
        return x;
    }
    else {
        y->lc = merge(x,y->lc);
        y->update();
        return y;
    }
}
void insert(const int &key)
{
    node *x,*y,*z;
    split(root,key,x,y);
    root = merge(merge(x,newnode(key)),y);
    return;
}
void erase(const int &key)
{
    node *x,*y,*z;
    split(root,key,x,z);
    split(x,key-1,x,y);
    if(y!=NULL)
        y = merge(y->lc,y->rc);  
    x = merge(x,y);
    root = merge(x,z);
    return;
}
int getnum(int rank)
{
    node *now = root;
    while(rank>0&&now!=NULL) {
        if(siz(now->lc)+1==rank) 
            break;
        if(siz(now->lc)+1 > rank) 
            now = now->lc;
        else 
            rank-=siz(now->lc)+1,now = now->rc;
    }
    return (now==NULL) ? 0 : now->val;
}
int getrank(const int &key)
{
    node *x,*y,*z;
    split(root,key-1,x,y);
    int tmp = siz(x)+1;
    root = merge(x,y);
    return tmp;
}
int getpre(const int &key)
{
    node *x,*y,*z;
    split(root,key-1,x,y);
    node *now = x;
    if(now==NULL) 
        return 1e7;
    while(now->rc!=NULL) 
        now = now->rc;
    root = merge(x,y);
    return now->val;
}
int getsuf(const int &key)
{
    node *x,*y,*z;
    split(root,key,x,y);
    node *now = y;
    if(now==NULL) 
        return -1e7;
    while(now->lc!=NULL)
        now = now->lc;
    root = merge(x,y);
    return now->val; 
}
int main()
{
    //  freopen("1.in","r",stdin);
    int n;
    scanf("%d",&n);
    int opt,x;
    while(n--) {
        scanf("%d%d",&opt,&x);
        switch(opt) {
            case 1 : insert(x); break;
            case 2 : erase(x); break;
            case 3 : printf("%d\n",getrank(x)); break;
            case 4 : printf("%d\n",getnum(x)); break;
            case 5 : printf("%d\n",getpre(x)); break; 
            case 6 : printf("%d\n",getsuf(x)); break;
        }   
    }
    //============================================
    return 0;
}

按大小分裂

适用于维护区间关系

实际上就改了 split

食用方式：

• 分裂出要修改的区间 split
• 打上标记
• 重新接进去 merge

伪码

void ...(int l,int r)
{
    int x,y,z;
    split(root,l-1,x,z);
    split(z,r-l+1,y,z);
    ...//此处打上标记
    z=merge(y,z);
    root=merge(x,z);
    return;
}

可以支持的标记有

• 区间修改（区间加，区间减，区间乘...）
• 区间赋值
• 区间翻转
• 区间最大子段和
• ....

（可以说线段树支持的操作，文艺平衡树都可以实现）。

再说一下 pushdown

原则上，在什么时候下传标记？

• 父节点要和子节点分开时（要下传子节点姗姗来迟的贡献）
• 查询时(...)
• ...

其实还能想到很多，但 fhptreap 的功能基本上是由 merge 和 split 实现的。

所以在这两个函数加上 pushdown 操作即可。

void split(int now,int siz,int &x,int &y)
{
    if(!now) {
        x=y=0;
        return;
    }
    pushdown(now);
    if(s(lc(now))+1<=siz) { 
        x=now;
        split(rc(now),siz-s(lc(now))-1,rc(x),y);
    }
    else {
        y=now;
        split(lc(now),siz,x,lc(y));
    }
    update(now);
    return;
}
int merge(int x,int y) //v(x)<=v(y)
{
    if(x==0||y==0) 
        return x+y;
    if(p(x)<p(y)) {
        pushdown(x);
        rc(x)=merge(rc(x),y);
        update(x);
        return x;
    }
    else {
        pushdown(y);
        lc(y)=merge(x,lc(y));
        update(y);
        return y;
    }
}

洛谷P3391 【模板】[文艺平衡树][https://www.luogu.com.cn/problem/P3391]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node 
{
    int lc,rc;
    int size; //子树大小 
    int val; //其实是序号 
    int pri;    //随机的优先级 
    bool reverse; //翻转懒标记 
    #define lc(x) t[x].lc
    #define rc(x) t[x].rc
    #define v(x) t[x].val
    #define s(x) t[x].size
    #define p(x) t[x].pri
    #define rs(x) t[x].reverse
};
node t[N];
int root,cnt;
void update(const int &now)
{
    s(now) = s(lc(now))+s(rc(now))+1;
    return;
}
int newnode(const int &key)
{
    ++cnt;
    v(cnt) = key;
    lc(cnt)=rc(cnt)=0;
    s(cnt)=1;
    p(cnt)=rand();
    return cnt;
}
void pushdown(int now)
{
    if(!rs(now)) return;
    swap(lc(now),rc(now));
    rs(lc(now))^=1;
    rs(rc(now))^=1;
    rs(now)=false;
    return;
}
void split(int now,int siz,int &x,int &y)
{
    if(!now) {
        x=y=0;
        return;
    }
    pushdown(now);
    if(s(lc(now))+1<=siz) { 
        x=now;
        split(rc(now),siz-s(lc(now))-1,rc(x),y);
    }
    else {
        y=now;
        split(lc(now),siz,x,lc(y));
    }
    update(now);
    return;
}
int merge(int x,int y) //v(x)<=v(y)
{
    if(x==0||y==0) 
        return x+y;
    if(p(x)<p(y)) {
        pushdown(x);
        rc(x)=merge(rc(x),y);
        update(x);
        return x;
    }
    else {
        pushdown(y);
        lc(y)=merge(x,lc(y));
        update(y);
        return y;
    }
}
void reverse(int l,int r)
{
    int x,y,z;
    split(root,l-1,x,y); 
    split(y,r-l+1,y,z);
    rs(y)^=1;
    y=merge(y,z);
    root=merge(x,y);
    return;
}
void ldr(int now)
{
    if(!now) return;
    pushdown(now);
    ldr(lc(now));
    printf("%d ",now);
    ldr(rc(now));
    return;
}
int main()
{
    int n,m;
    int l,r;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        root=merge(root,newnode(i));
    } 
    while(m--) {
        scanf("%d%d",&l,&r);    
        reverse(l,r);
    }
    ldr(root);
    return 0;
}

P2710 数列

(这道题基本上实现了文艺平衡树的所有操作)

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
#define int LL 
inline void read(LL &x)
{
    x=0;
    char c=getchar();
    bool sign=false;
    while(c<'0'||c>'9') {
        if(c=='-') sign=true;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }
    if(sign) x=~x+1;
    return;
}
short bcc[22],top=0;
inline void print(LL x)
{
    top=0;
    if(!x) {
        putchar('0');
        return;
    }
    if(x<0) putchar('-'),x=~x+1;
    while(x) {
        bcc[++top]=x%10;
        x=x/10;
    }
    while(top>=1) {
        putchar(48+bcc[top]);
        --top;
    }
    return;
}
inline LL max(const LL &x,const LL &y)
{
    if(x>y) return x;
    else return y;
}
inline void swap(LL &x,LL &y)
{
    x^=y^=x^=y;
    return;
}
const LL INF=1e17;
const int N=1000000+5;
struct node
{
    int lc,rc;
    LL val;
    int size;
    bool reverse;
    LL tag;
    LL sum,qm,ql,qr;
    int pri;
    #define lc(x) t[x].lc
    #define rc(x) t[x].rc
    #define v(x) t[x].val
    #define s(x) t[x].size
    #define rv(x) t[x].reverse
    #define tag(x) t[x].tag
    #define sum(x) t[x].sum
    #define qm(x) t[x].qm
    #define ql(x) t[x].ql
    #define qr(x) t[x].qr
    #define pri(x) t[x].pri
};
node t[N];
int root=0,cnt=0;
int Qdel[N],len=0;
LL a[N];
inline void update(const int &x)
{
    s(x)=s(lc(x))+s(rc(x))+1;
    sum(x)=sum(lc(x))+sum(rc(x))+v(x);
    qm(x)=max(qr(lc(x))+v(x),ql(rc(x))+v(x));
    if(lc(x)) qm(x)=max(qm(x),qm(lc(x)));
    if(rc(x)) qm(x)=max(qm(x),qm(rc(x)));
    qm(x)=max(qm(x),qr(lc(x))+v(x)+ql(rc(x)));
    qm(x)=max(qm(x),v(x));
    ql(x)=max(ql(lc(x)),sum(lc(x))+v(x));
    ql(x)=max(ql(x),sum(lc(x))+v(x)+ql(rc(x)));
    qr(x)=max(qr(rc(x)),sum(rc(x))+v(x));
    qr(x)=max(qr(x),qr(lc(x))+sum(rc(x))+v(x));
    return;
}
inline void Addtag(const int &now,const LL &key)
{
    if(!now) return;
    rv(now)=false;
    v(now)=key;
    tag(now)=key;
    sum(now)=key*s(now);
    if(tag(now)>=0) qr(now)=ql(now)=qm(now)=sum(now);
    else qr(now)=ql(now)=qm(now)=key;       
    return;
}
inline void Addreverse(const int &now)
{
    if(!now||tag(now)!=INF) return;
    rv(now)^=1;
    swap(ql(now),qr(now));
    swap(lc(now),rc(now));
    return;
}
inline void push_down(const int &now)
{
    if(!now) return;
    if((!lc(now))&&(!rc(now))) {
        rv(now)=false;
        tag(now)=INF;
        return;
    }
    if(tag(now)!=INF) rv(now)=false; 
    if(rv(now)) {
        if(lc(now)) Addreverse(lc(now));
        if(rc(now)) Addreverse(rc(now));
        rv(now)=false;
    }
    if(tag(now)!=INF) {
        if(lc(now)) Addtag(lc(now),tag(now));
        if(rc(now)) Addtag(rc(now),tag(now));
        tag(now)=INF;
    }
    return;
}
inline int newnode(const LL &key)
{
    int now;
    if(len>=1) now=Qdel[len--];
    else now=++cnt;
    lc(now)=rc(now)=0;
    s(now)=1;
    rv(now)=false;
    tag(now)=0;
    pri(now)=rand();
    qm(now)=qr(now)=ql(now)=sum(now)=v(now)=key;
    return now;
}
void split(int now,int rank,int &x,int &y) //<= >
{
    if(!now) { 
        x=y=0;
        return;
    }
    push_down(now);
    if(s(lc(now))+1<=rank) {
        x=now;
        split(rc(now),rank-s(lc(now))-1,rc(now),y);
    }
    else {
        y=now;
        split(lc(now),rank,x,lc(y));
    }
    update(now);
    return;
}
int merge(int x,int y) //x<=y
{
    if(x==0||y==0) 
        return x+y;
    if(pri(x)>pri(y)) {
        push_down(x);
        rc(x)=merge(rc(x),y);
        update(x);
        return x;
    }
    else {
        push_down(y);
        lc(y)=merge(x,lc(y));
        update(y);
        return y;
    }
}
int Build(int l,int r)
{
    if(l==r)    
        return newnode(a[l]);
    int x,mid=(l+r)>>1;
    x=merge(Build(l,mid),Build(mid+1,r));
    return x;
}
void recycle(int now)
{
    if(!now) 
        return;
    Qdel[++len]=now;
    recycle(rc(now));
    recycle(lc(now));
    return;
}
char opt[10];
int n,m;
#define rint register int 
signed main()
{
//  freopen("1.in","r",stdin);
    srand(20040524);
    rint i;
    LL x,y,z,pos,tot,val;
    read(n); read(m);
    for(i=1;i<=n;i++) 
        read(a[i]);
    root=Build(1,n);
    qm(0)=-INF;
    while(m--) {
        scanf("%s",opt+1);
        x=y=z=0;
        if(opt[1]=='I') {
            read(pos); read(tot);
            for(i=1;i<=tot;i++)
                read(a[i]);
            split(root,pos,x,z);
            root=merge(merge(x,Build(1,tot)),z);
        }
        else if(opt[1]=='D') {
            read(pos); read(tot);
            split(root,pos-1,x,z);
            split(z,tot,y,z);
            recycle(y);
            root=merge(x,z);
        }
        else if(opt[1]=='M'&&opt[3]=='K') {
            read(pos); read(tot); read(val);
            split(root,pos-1,x,z);
            split(z,tot,y,z);
            Addtag(y,val);
            z=merge(y,z);
            root=merge(x,z);
        }
        else if(opt[1]=='R') {
            read(pos); read(tot);
            split(root,pos-1,x,z);
            split(z,tot,y,z);
            Addreverse(y);
            z=merge(y,z);
            root=merge(x,z);
        }
        else if(opt[1]=='G'&&strlen(opt+1)==7) {
            read(pos); read(tot);
            split(root,pos-1,x,z);
            split(z,tot,y,z);
            print(sum(y)); putchar('\n');
            z=merge(y,z);
            root=merge(x,z);
        }
        else if(opt[1]=='G') {
            read(pos);
            split(root,pos-1,x,z);
            split(z,1,y,z);
            print(v(y)); putchar('\n');
            z=merge(y,z);
            root=merge(x,z);
        }
        else {
            read(pos); read(tot);
            split(root,pos-1,x,z);
            split(z,tot,y,z);
            print(qm(y)),putchar('\n');
            z=merge(y,z);
            root=merge(x,z);
        }
    }
    return 0;
}

外谈

1.建树的技巧

适用范围：多次重新建树或在文艺平衡树中连续插入多个数

与线段树建树类似，

int Build(int l,int r)
{
    if(l==r)    
        return newnode(a[l]);
    int x,mid=(l+r)>>1;
    x=merge(Build(l,mid),Build(mid+1,r));
    return x;
}

这样建出来的平衡树是完全平衡的。

时间复杂度：O(n)

2.动态开存大法

适用范围：总元素数量不确定，带有大量的删除和插入

即把删除元素的下标存在一个栈或队列里，由 newnode 取走。

inline int newnode(const LL &key)
{
    int now;
    if(len>=1) now=Qdel[len--];
    else now=++cnt;
    lc(now)=rc(now)=0;
    s(now)=1;
    rv(now)=false;
    tag(now)=0;
    pri(now)=rand();
    qm(now)=qr(now)=ql(now)=sum(now)=v(now)=key;
    return now;
}

//删除整段---文艺平衡树
split(root,pos-1,x,z);
split(z,tot,y,z);
recycle(y);
root=merge(x,z);

//删除单个元素---普通平衡树
split(root,key-1,x,z)
split(z,key,y,z);
Qdel[++len]=y;
y=merge(lc(y),rc(y));
z=merge(y,z);
root=merge(x.z);

回收函数 recycle

void recycle(int now)
{
    if(!now) 
        return;
    Qdel[++len]=now;
    recycle(rc(now));
    recycle(lc(now));
    return;
}

具体见 P2710 数列

3.关于合并

例题-永无乡

可以使用启发式合并

还可以用我想出的诡异方式合并

int set_merge(int x,int y)
{
    if(x==0||y==0) 
        return x+y;
    int u,v;    
    if(p(x)*s(x)<p(y)*s(y)) 
        swap(x,y);
    split(y,v(x)-1,u,v);
    lc(x)=set_merge(lc(x),u);
    rc(x)=set_merge(rc(x),v);
    update(x);
    return x;
}

貌似更快一点

详见我的代码

https://github.com/cjlworld/OJ/blob/master/P3224.cpp