简单平衡树—Treap的模板与运用

考试之前再摸了一摸Treap。

大概是联赛需要记的最长的代码了吧(这辈子没能力在考场手打Splay)orz。


Treap简介

所谓Treap,即是Tree+Heap的结合产物。
众所周知,普通BST在维护的时候可能因为插入有序的数据而导致查询时间退化为线性。所以各种神仙平衡树应运而生。
带旋转的Treap是我接触最早的平衡树,也是所有平衡树中最为好打的一种。
最为重要的操作无非是:

  • 新增节点:声明一个新的变量,除了左右儿子和值这种常规变量之外,还需要记录当前值的个数,当前子树的大小,以及专用于Treap的优先级变量,用于维护Treap中值的堆序
  • 旋转节点:将某个节点旋转自己的左方或者右方,在保证BST性质不变的情况下调整了优先级的顺序,使其符合堆序
  • 插入节点:先在树中按BST的方式找节点,找到则将其数量加一,未找到则新建节点,并让其向上旋转直到符合堆序
  • 删除节点:先在树中按BST的方式找节点,数量大于一则数量减一,否则就将其旋转到叶子节点然后清空
  • 查询前驱,后继,名次,值与普通BST大同小异

下面会放出代码模板,模板后是经典例题的解析。

代码模板

(Tyvj1728) 【模板】普通平衡树

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1.插入xx数
2.删除xx数(若有多个相同的数,因只删除一个)
3.查询xx数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数,因输出最小的排名)
4.查询排名为xx的数
5.求xx的前驱(前驱定义为小于xx,且最大的数)
6.求xx的后继(后继定义为大于xx,且最小的数)

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
const ll LIM=1000010;
const ll INF=0x7ffffffffffffff;
struct Node{
    Node():l(0),r(0),val(0),dat(0),cnt(0),size(0){}
    ll l,r,val,dat,cnt,size;
};
class Treap{
    public:
        Treap();
        ll GetVal(ll rank);//获取第rank名的数 
        ll GetRank(ll val);//获取值val的排名 
        ll Insert(ll val);//插入值val 
        ll GetPre(ll val);//获取小于val最大的数 
        ll GetNext(ll val);//获取大于val最小的数 
        ll Erase(ll val);//删除一个值为val的数
        bool Exist(ll val);//判断val是否存在
        bool Empty();//判断是否为空 
        ll GetMin();//获取最小值 
        ll GetMax();//获取最大值 
        ll GetSize();//获取当前节点数 
    private:
        void update(ll u);//更新节点 
        ll add(ll val);//新增节点 
        void zig(ll &u);//右旋 
        void zag(ll &u);//左旋 
        ll _getval(ll u,ll rank);
        ll _getrank(ll u,ll val);
        void _insert(ll &u,ll val);
        void _erase(ll &u,ll val);
        bool _exist(ll u,ll val);
        Node eds[LIM];//数组模拟链表 
        ll et,root;//节点个数,根 
};
Treap::Treap(){
    et=0;
    root=add(-INF);
    eds[root].r=add(INF);
    update(root);
}
#define L eds[u].l
#define R eds[u].r
#define V eds[u].val
void Treap::update(ll u){
    eds[u].size=eds[L].size+eds[R].size+eds[u].cnt;
}
ll Treap::add(ll val){
    eds[++et].val=val;
    eds[et].dat=rand();
    eds[et].cnt=eds[et].size=1;
    return et;
}
void Treap::zig(ll &u){
    ll t=L;
    L=eds[t].r,eds[t].r=u,u=t;
    update(R),update(u);
}
void Treap::zag(ll &u){
    ll t=R;
    R=eds[t].l,eds[t].l=u,u=t;
    update(L),update(u);
}
ll Treap::_getrank(ll u,ll val){
    if(!u)return 0;
    if(val==V)return eds[L].size+1;
    if(val<V)return _getrank(L,val);
    return _getrank(R,val)+eds[L].size+eds[u].cnt;
}
ll Treap::_getval(ll u,ll rank){
    if(!u)return INF;
    if(eds[L].size>=rank)return _getval(L,rank);
    if(eds[L].size+eds[u].cnt>=rank)return V;
    return _getval(R,rank-eds[L].size-eds[u].cnt);
}
ll Treap::GetRank(ll val){
    return _getrank(root,val)-1;
}
ll Treap::GetVal(ll rank){
    return _getval(root,rank+1);
}
void Treap::_insert(ll &u,ll val){
    if(!u){u=add(val);return;}
    if(val==V)eds[u].cnt++;
    else if(val<V){
        _insert(L,val);
        if(eds[u].dat<eds[L].dat)zig(u);
    }else{
        _insert(R,val);
        if(eds[u].dat<eds[R].dat)zag(u);
    }
    update(u);
}
ll Treap::Insert(ll val){
    _insert(root,val);
    return val;
}
ll Treap::GetPre(ll val){
    ll res=1,u=root;
    while(u){
        if(val==V){
            if(L){u=L;while(R)u=R;res=u;}
            break;
        }
        if(V<val&&V>eds[res].val)res=u;
        u=val<V?L:R;
    }
    return eds[res].val;
}
ll Treap::GetNext(ll val){
    ll res=2,u=root;
    while(u){
        if(val==V){
            if(R){u=R;while(L)u=L;res=u;}
            break;
        }
        if(V>val&&V<eds[res].val)res=u;
        u=val<V?L:R;
    }
    return eds[res].val;
}
void Treap::_erase(ll &u,ll val){
    if(!u)return;
    if(val==V){
        if(eds[u].cnt>1){
            eds[u].cnt--;
            update(u);
            return;
        }
        if(L||R){
            if(!R||eds[L].dat>eds[R].dat)
                zig(u),_erase(R,val);
            else
                zag(u),_erase(L,val);
            update(u);
        }else u=0;
        return;
    }
    val<V?_erase(L,val):_erase(R,val);
    update(u);
}
ll Treap::Erase(ll val){
    _erase(root,val);
    return val;
}
bool Treap::_exist(ll u,ll val){
    if(!u)return false;
    if(val==V)return true;
    return val<V?_exist(L,val):_exist(R,val);
}
bool Treap::Exist(ll val){
    return _exist(root,val);
}
bool Treap::Empty(){
    return eds[root].size==2;
}
ll Treap::GetMin(){
    return GetNext(-INF+1);
}
ll Treap::GetMax(){
    return GetPre(INF-1);
}
ll Treap::GetSize(){
    return eds[root].size-2;
} 
//-------------------------------------

Treap tp;
ll n;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    ll op,x;
    while(n--){
        cin>>op>>x;
        switch(op){
            case 1:tp.Insert(x);break;
            case 2:tp.Erase(x);break;
            case 3:cout<<tp.GetRank(x)<<'\n';break;
            case 4:cout<<tp.GetVal(x)<<'\n';break;
            case 5:cout<<tp.GetPre(x)<<'\n';break;
            case 6:cout<<tp.GetNext(x)<<'\n';break;
            default:break;
        }
    }
    return 0;
}

经典例题

[HNOI2002]营业额统计

Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况:
当最小波动值越大时,就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。

  • 本题几乎就是完全的模板
  • 对于每个营业额,在Treap中查询有没有相同的,有就跳过。若无,查询前驱后继,取差距小的那个
[HNOI2004]宠物收养场

凡凡开了一间宠物收养场。收养场提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。
每个领养者都希望领养到自己满意的宠物,凡凡根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了,宠物收养场总是会有两种情况发生:被遗弃的宠物过多或者是想要收养宠物的人太多,而宠物太少。
被遗弃的宠物过多时,假若到来一个领养者,这个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。(任何两只宠物的特点值都不可能是相同的,任何两个领养者的希望领养宠物的特点值也不可能是一样的)如果有两只满足要求的宠物,即存在两只宠物他们的特点值分别为a-b和a+b,那么领养者将会领养特点值为a-b的那只宠物。
收养宠物的人过多,假若到来一只被收养的宠物,那么哪个领养者能够领养它呢?能够领养它的领养者,是那个希望被领养宠物的特点值最接近该宠物特点值的领养者,如果该宠物的特点值为a,存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b,那么特点值为a-b的那个领养者将成功领养该宠物。
一个领养者领养了一个特点值为a的宠物,而它本身希望领养的宠物的特点值为b,那么这个领养者的不满意程度为abs(a-b)。
你得到了一年当中,领养者和被收养宠物到来收养所的情况,请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时,收养所里面既没有宠物,也没有领养者。你得到了一年当中,领养者和被收养宠物到来收养所的情况,请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时,收养所里面既没有宠物,也没有领养者。

  • 略带技巧的模板题。
  • 由于同一时刻只可能有宠物或者领养者,所以只需要一个Treap。记录一个布尔量代表此时Treap中是宠物还是领养者。之后就如同上面那道题,若当前Treap里的东西和自己相符就插入,否则查询存在,再查询前驱后继,最后删除。
[NOI2004]郁闷的出纳员

OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。
好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?
如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

  • 略带技巧的模板题
  • 考虑对所有在职员工维护一个Treap,并用一个量表示现在累计的增减工资量。入职时先判断是否小于工资标准,由于之前的增减与其无关,插入时减去当前累计量方便判断。
  • 之后若减工资更新累积量,查询最小值,加上累积量后是否小于工资标准,弹出。一直找到符合标准或者空了为止。
  • 注意查询第k名时需要先判断Treap中的节点个数

那么Treap到这里就讲完啦!!

祝各位都可以在赛场上一字不差完美地打出它!


发表评论

电子邮件地址不会被公开。 必填项已用*标注