注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

Treap模板(有待完善中)  

2014-02-17 18:49:49|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
-------------------------------------------------------------------------------------------
话说当时之所以选择Treap作为第一个自己掌握的二叉查找树
就是因为Treap比Splay短不少 
当然可参考的东西也多些
建议参考
1.郭家宝(by void)的论文
4.ACM的模板
-------------------------------------------------------------------------------------------
进阶
-------------------------------------------------------------------------------------------
最基本的treap(tyvj普通平衡树那题 求神犇看了后提些建议以助完善)
-------------------------------------------------------------------------------------------
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
#define rep(i,n) for(int i=1;i<=n;++i)
using namespace std;
const int N=100010,BIG=2000000000;
struct treap
{
    int child[2],num,aux;///num为该节点的值,aux为随机出来的优先级
    int sum,same;///same为该节点的数的个数,sum为该节点及所有子树的数的个数
}a[N];
int n,len,root;
void yuchuli()///预处理
{
    root=0;
    len=0;
    /*a[0].num=BIG;
    a[0].same=1;
    a[0].aux=-BIG;*///这一块写和不写都没多大差别 不过有时候会有题目需要用到固定树根的技巧
}
void update_treap(int x)///维护sum
{
    a[x].sum=a[a[x].child[0]].sum+a[a[x].child[1]].sum+a[x].same;
}
void rotate_treap(int &x,int t)///左右旋转
{
    int y=a[x].child[t];
    a[x].child[t]=a[y].child[t^1];
    a[y].child[t^1]=x;
    update_treap(x);
    update_treap(y);
    x=y;///把指向x的指向y?我指针好渣。。
}
void insert_treap(int &x,int y)///插入节点
{
    if(x)
    {
        if(a[x].num==y)
            ++a[x].same;
        else
        {
            int t=a[x].num<=y;
            insert_treap(a[x].child[t],y);
            if(a[a[x].child[t]].aux<a[x].aux)
                rotate_treap(x,t);
        }
    }
    else
    {
        x=++len;
        a[x].num=y;
        a[x].same=1;
        a[x].aux=rand();
        if(a[x].aux<-BIG)
            a[x].aux+=BIG;
    }
    update_treap(x);
}
void delete_treap(int &x,int y)///删除节点
{
    if(a[x].num==y)
    {
        if(a[x].same>1)
            --a[x].same;
        else
        {
            if(!a[x].child[0]&&!a[x].child[1])
            {
                x=0;
                return;
            }
            if(a[x].child[0]&&!a[x].child[1])
            rotate_treap(x,0);
            else if(!a[x].child[0]&&a[x].child[1])
            rotate_treap(x,1);
            else
            {
                int t=a[a[x].child[0]].aux>a[a[x].child[1]].aux;
                rotate_treap(x,t);
            }
            delete_treap(x,y);
        }
    }
    else
    delete_treap(a[x].child[a[x].num<y],y);
    update_treap(x);
}
int kth_treap(int &x,int y)///求第y大的数
{
    if(y<=a[a[x].child[0]].sum)
    return kth_treap(a[x].child[0],y);
    y-=a[a[x].child[0]].sum+a[x].same;
    if(y<=0)return a[x].num;
    return kth_treap(a[x].child[1],y);
}
int rank_treap(int &x,int y,int rr)///求y的排名(数值越小排名越靠前)
{
    if(y==a[x].num)
    {
        if(a[x].child[0])
            rr+=a[a[x].child[0]].sum;
        return rr+1;
    }
    int t=y>a[x].num;
    if(t)rr+=a[a[x].child[0]].sum+a[x].same;
    return rank_treap(a[x].child[t],y,rr);
}
int pre_treap(int &x,int y,int tmp)///求小于y的最大数
{
    if(!x)
        return tmp;
    if(a[x].num<y)
    return pre_treap(a[x].child[1],y,a[x].num);
    return pre_treap(a[x].child[0],y,tmp);
}
int next_treap(int &x,int y,int tmp)///求大于y的最小数
{
    if(!x)
        return tmp;
    if(a[x].num>y)
    return next_treap(a[x].child[0],y,a[x].num);
    return next_treap(a[x].child[1],y,tmp);
}
int main()
{
    scanf("%d",&n);
    int ch,x;
    yuchuli();
    srand(0);///如果用time(0)的话 要加ctime 但是time(0)有可能RE(比如BZOJ上)然后这里的随机 不是随机数据 而是只要保持平衡即可 所以就。。。
    rep(i,n)
    {
        scanf("%d%d",&ch,&x);
        if(ch==1)
        insert_treap(root,x);
        else if(ch==2)
        delete_treap(root,x);
        else if(ch==3)
        printf("%d\n",rank_treap(root,x,0));
        else if(ch==4)
        printf("%d\n",kth_treap(root,x));
        else if(ch==5)
        printf("%d\n",pre_treap(root,x,-BIG));
        else
        printf("%d\n",next_treap(root,x,-BIG));
    }
    return 0;
}
-------------------------------------------------------------------------------------------
目前还没有合并和分裂部分(话说当时决定学平衡树就是因为
线段树不方便合并和分裂
(当然最主要的就是不支持在线 不过一般很少有强制在线的题))
所以 多做几个题后试着把合并和分裂加上
-------------------------------------------------------------------------------------------
更新部分:
void merge_treap(int &x,int y)///启发式合并 y为要合并到的数
{
    if(x)
    {
        merge_treap(a[x].child[0],y);
        merge_treap(a[x].child[1],y);///由于是指针传递 所以这两个函数一定要在insert前
        if(a[x].aux!=MIN)
        insert_treap(y,a[x].num);
    }
}
  评论这张
 
阅读(72)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017