文档章节

【bzoj1728】普通平衡树

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 622
阅读 3
收藏 0

到现在才想起来我还不会写splay……
QAQ
在DQS学长写模板的时候带了我下……
QAQ人生第一个维护数的splay
QAQQQQQQQ

要记得在del、rot、newnode这种设计更新根的操作的时候一定要root = x;root -> f = null

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
struct tr
{
    tr *ch[2],*f;
    int v,sz,cnt;
    bool dir()
    {
        return f -> ch[1] == this;
    }
    void maintain()
    {
        sz = cnt + ch[0] -> sz + ch[1] -> sz;
        return;
    }
    void setc(tr *p,int d)
    {
        (ch[d] = p) -> f = this;
        return;
    }
}tree[MAXN],*root,*null;
int tot = 0;
tr* newnode(int x,tr* fa = null)
{
    tr *p = tree + (tot ++);
    p -> f = fa;
    p -> ch[0] = p -> ch[1] = null;
    p -> sz = p -> cnt = 1;
    p -> v = x;
    return p;
}
void reset()
{
    tot = 0;
    null = newnode(0);
    null -> sz = null -> cnt = 0;
    root = null;
    return;
}
void rot(tr *x)
{
    tr *p = x -> f;
    int d = x -> dir();
    p -> f -> setc(x,p -> dir());
    p -> setc(x -> ch[d ^ 1],d);
    p -> maintain();
    x -> setc(p,d ^ 1);
    x -> maintain();
    if(p == root)
        root = x;
    return;
}
void splay(tr* x,tr* to = null)
{
    while(x -> f != to)
    {
        if(x -> f -> f == to)
            rot(x);
        else
            x -> dir() == x -> f -> dir() ? (rot(x -> f),rot(x)) : (rot(x),rot(x));
    }
}
void insert(int x)
{
    if(root == null)
    {
        root = newnode(x);
        return;
    }
    tr* p = root;
    while(p != null)
    {
        p -> sz ++;
        if(p -> v == x)
        {
            p -> cnt++;
            break;
        }
        int d = x > p -> v;
        if(p -> ch[d] == null)
        {
            p -> ch[d] = newnode(x,p);
            p = p -> ch[d];
            break;
        }
        p = p -> ch[d];
    }
    splay(p);
    return;
}
tr* find(int x)
{
    tr* p = root;
    while(p != null)
    {
        if(p -> v == x)
            break;
        int d = x > p -> v;
        p = p -> ch[d];
    }
    splay(p);
    return p;
}
void del(int x)
{
    tr *p = find(x);
    splay(p);
    p -> sz --;
    if(--p -> cnt)
        return;
    if(p -> ch[0] == null){root = p -> ch[1];root -> f = null;return;}
    if(p -> ch[1] == null){root = p -> ch[0];root -> f = null;return;}
    p = p -> ch[0];
    while(p -> ch[1] != null)
        p = p -> ch[1];
    splay(p,root);
    p -> setc(root -> ch[1],1);
    p -> f = null;
    p -> maintain();
    root = p;
    return;
}
int find_hj(int x)
{
    tr* p = root;
    int ans = 0;
    while(p != null)
    {
        if(x < p -> v)
            ans = p -> v,p = p -> ch[0];
        else
            p = p -> ch[1];
    }
    return ans;
}
int find_qq(int x)
{
    tr* p = root;
    int ans = 0;
    while(p != null)
    {
        if(x > p -> v)
            ans = p -> v,p = p -> ch[1];
        else
            p = p -> ch[0];
    }
    return ans;
}
int num_to_pm(int x)
{
    splay(find(x));
    return root -> ch[0] -> sz + 1;
}
int pm_to_num(int x)
{
    tr* p = root;
    while(p != null)
    {
        int l = p -> ch[0] -> sz + 1;
        int r = p -> ch[0] -> sz + p -> cnt;
        if(l <= x && x <= r)
            return p -> v;
        int d = x > p -> ch[0] -> sz + p -> cnt;
        if(d)
            x -= p -> ch[0] -> sz + p -> cnt;
        p = p -> ch[d];
    }
    return p -> v;
}

int n,q,x;
int main()
{
    reset();
    scanf("%d",&n);
    while(n --)
    {
        scanf("%d",&q);
        switch(q)
        {
            case 1:scanf("%d",&x);insert(x);break;
            case 2:scanf("%d",&x);del(x);break;
            case 3:scanf("%d",&x);printf("%d\n",num_to_pm(x));break;
            case 4:scanf("%d",&x);printf("%d\n",pm_to_num(x));break;
            case 5:scanf("%d",&x);printf("%d\n",find_qq(x));break;
            case 6:scanf("%d",&x);printf("%d\n",find_hj(x));break;
        }
    }
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
自己动手实现java数据结构(七) AVL树

1.AVL树介绍   前面我们已经介绍了二叉搜索树。普通的二叉搜索树在插入、删除数据时可能使得全树的数据分布不平衡,退化,导致二叉搜索树最关键的查询效率急剧降低。这也引出了平衡二叉搜索...

小熊餐馆
02/13
0
0
《算法导论》学习笔记之Chapter13红黑树

第13章 红黑树 红黑树是一种平衡搜索树中的一种,他可以保证在最坏情况下基本动态集合操作时间复杂度为O(logn)。所以,在学习红黑树之前,我需要先去调研一下平衡树; 先看一下平衡树的定义:...

u010483897
2017/12/13
0
0
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
0
1
TYVJ1728普通平衡树题解(Treap学习笔记)

TYVJ1728普通平衡树题解(Treap学习笔记) 题意: 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个)...

AndyGamma
2018/09/06
0
0
12.1 省选训练总结2(1) 点分治/平衡树

目录 点分治 Splay 完成情况截图 聪聪可可 普通平衡树 文艺平衡树 宠物收养所 Cards Sorting 点分治 首先找重心,然后对过了重心的路径计算,最后递归点分。 前4道题是点分裸题,就不赘述。 ...

OwenOwl
2017/12/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

线程池之ThreadPoolExecutor使用

ThreadPoolExecutor提供了四个构造方法: ThreadPoolExecutor构造方法.png 我们以最后一个构造方法(参数最多的那个),对其参数进行解释: public ThreadPoolExecutor(int corePoolSize, /...

天王盖地虎626
23分钟前
1
0
小程序登陆流程

http://www.bubuko.com/infodetail-2592845.html

为何不可1995
32分钟前
1
0
Consul+Spring boot的服务注册和服务注销

一图胜千言 先看一看要做事情,需要在Consul上面实现注册中心的功能,并以2个Spring boot项目分别作为生产者,消费者。 Consul 假设已经完成文章《Consul的开发者模式之Docker版》中的所有的...

亚林瓜子
38分钟前
4
0
MySQL高可用之基于Galera复制跨地域节点分布的滥用

mysql使用教程 MySQL高可用之基于Galera复制跨地域节点分布的滥用 2018-11-22 02:15 8335 85 让我们再一次讨论MySQL高可用性(HA)和同步复制。 它是地理上分布区域上一些高可用性参考架构解...

rootliu
49分钟前
1
0
js判断pc还是移动端

var pcyidong =/(iPhone|iPad|iPod|iOS|Android)/i.test(navigator.userAgent); 如果pcyidong的值为false则用户的浏览器为pc端 如果pcyidong的值为true则用户浏览器为移动端 if (pcyidong =...

流年那么伤
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部