题目名称 1829. [Tyvj 1728]普通平衡树
输入输出 phs.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 1000 MB
测试数据 10 简单对比
题目来源 2014-11-30
开放分组 全部用户
提交状态
分类标签
通过:262, 提交:3219, 通过率:8.14%
GravatarZlycerQan 100 0.085 s C++
GravatarLazer2001 100 0.095 s C++
GravatarLazer2001 100 0.095 s C++
GravatarLazer2001 100 0.095 s C++
GravatarLazer2001 100 0.095 s C++
GravatarLazer2001 100 0.095 s C++
GravatarLazer2001 100 0.096 s C++
GravatarLazer2001 100 0.096 s C++
GravatarLazer2001 100 0.096 s C++
GravatarLazer2001 100 0.096 s C++
关于 普通平衡树 的讨论
著名的平衡树模板题,欢迎各种姿势练习
替罪羊树代码:替罪羊树代码
Treap代码:Treap代码
都不好写,都比splay好写,效率差不多
本题中Treap不需要存父亲,所以旋转比splay简单得多,替罪羊树没有旋转但需要写rebuild
Treap的旋转行数小于替罪羊的rebuild行数,同时带来一个福利:delete稍简单一些,但Treap需要时刻记得维护堆序性和update,看你选哪个了
另外,网上好几份标程在linux评测环境下都过不了是闹哪样啊(╯‵□′)╯︵┻━┻
Gravatarcstdio
2014-11-30 19:06 1楼
TAT决定推掉重写了= =
GravatarAsm.Def
2014-11-30 21:41 2楼
Treap终于搞定了QAQ表示写数据结构的时候不专心真是作死。。。太难调试了……
不过这次收获挺大的……研究出了一种很逗却很有效的调试技巧 →_→
GravatarAsm.Def
2014-12-01 21:25 3楼
回复 @Asm.Def :
写成DFS不就行了……见我的代码……
Gravatarcstdio
2014-12-01 22:14 4楼
回复 @cstdio :
可我感觉dfs看起来没有层次感……所以要写bfs(NULL也要输出来……)
GravatarAsm.Def
2014-12-01 22:38 5楼
回复 @CreationAugust :
有可能是类似a[-1]的问题,COGS采用的是Linux评测环境
Gravatarcstdio
2014-12-06 21:26 6楼
GravatarRP++
2015-03-17 17:12 7楼
回复 @真呆菌dsb :
set的iterator居然可以直接相减?Orzzzzzzzzzzzzzzzzz
(好吧看错容器了不要理我)(那么问题来了……这题用线性表都可以过吗。。。)
GravatarAsm.Def
2014-12-14 21:12 8楼
回复 @真呆菌dsb :
GravatarRP++
2015-03-17 17:12 9楼
这题数据不科学!我最后交了一份普通二叉树,也可以过……(其实只是把insert处的平衡操作注释掉了)
GravatarAsm.Def
2014-12-14 10:39 10楼
用之前的Treap代码改造出了个Size Balanced Tree /*,运行时间居然完全一样→_→ */
之前的Treap代码
//今天改造的SBT代码(误)
百度百科真是不靠谱。。。上面那个不是真的SBT……如果有极端数据的话这个有可能会被卡。。
这个才是真的SBT
然后关于一些同学SBT爆零的问题(@CreationAugust @dr98 )……我今天调试SBT的时候发现……叫"maintain()"的函数似乎已经被编译器占用了……这里换成“Maintain”就秒掉了= =
GravatarAsm.Def
2014-12-18 18:45 11楼
回复 @Asm.Def :
调了这么久的代码,原来TMD是那错了...
再也不写小写字母的函数了...
伤心了
Linux 怎么能这么坑!!!!!!!
GravatarJSX
2014-12-18 09:48 12楼
所以用汇编级别的快速读入可是够快的。。。(节操呢!)
GravatarAsm.Def
2015-01-07 22:44 13楼
呼。。。终于不看模版A了,第一次写指针有点呵呵。。。调了好长时间。。最后还加了读入优化。。。真是有些无耻。。。。PS:十分感谢hzwer神犇的Treap模版!
Gravatar小DOTA
2015-01-12 21:47 14楼
pb_ds来一发,常数大如狗,求常数帝@Asm.Def 轻虐……
Gravatarcstdio
2015-02-24 10:20 15楼
原谅我的无知QAQ
Gravatarztx
2015-04-01 21:12 16楼
处理重点恶心死我了
Gravatar清羽
2015-04-10 21:31 17楼
Gravatar一個人的雨
2015-12-26 11:26 18楼
丧心病狂的替罪羊树
Gravatarstdafx.h
2015-12-12 19:49 19楼
SBT为啥wa啊!!!下下来一个点,跑的答案都一样,只有空格的问题,总共3个答案竟然多了4个回车,但是这并不是重点啊!!!求大牛解释啊!!!
Gravatarnieyunhe
2016-01-02 11:24 20楼
回复 @nieyunhe :
评测姬是linux,你检查下诸如初始化/rand范围/数组越界这种问题……
Gravatarcstdio
2016-01-02 11:33 21楼
回复 @cstdio :
找到问题了!!!Windows下函数有一个神奇的特性,见code,如果不加注释掉的一句也可以输出答案,但是在LINUX下狂WA。。。

inline int suc(int &x,int d)//返回值d的后继权值;
{
if(!x)return d;
if(d>=tr[x].val)return suc(tr[x].rs,d);
else
{
int ans=suc(tr[x].ls,d);
if(ans==d)return tr[x].val;
// else return ans;
}
}
Gravatarnieyunhe
2016-01-02 15:19 22楼
仿制神犇代码成功
Gravatarmikumikumi
2016-04-10 21:26 23楼
给评测环境跪了。。。好不容易写出的treap,在BZOJ和TOJ上都过了,在这儿就超时。。好像是maintainup()超了
Gravatarliu_runda
2016-04-20 12:29 24楼
把maintainup由递归版改成迭代版就过了,不知道为啥。。。
Gravatarliu_runda
2016-04-20 16:35 25楼
GravatarAntiLeaf
2017-05-25 15:51 26楼
SPLAY
Gravatar粘粘自喜
2016-05-29 20:58 27楼
GravatarAntiLeaf
2017-05-25 15:59 28楼
1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值,而且它的根节点
的修正值小于等于左子树根节点的修正值;
2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值,而且它的根节点
的修正值小于等于右子树根节点的修正值;
3. 它的左、右子树也分别为Treap。
GravatarSOBER GOOD BOY
2016-07-11 06:25 29楼
平衡树 附加域 平衡性 运行效率 编程难度 实用性9 特性
Treap 修正值 较好 较快 易 好 随机平衡
BST 无 差 不稳定 易 一般 编写容易
Splay 无 - 中 中 好 灵活易变
AVL 子树高度 好 快 难 较差 经典算法
红黑树 节点颜色 好 快 难 较差 效率极佳
SBT 子树大小 好 快 中 好 短小精悍
GravatarSOBER GOOD BOY
2016-07-11 06:36 30楼
GravatarAntiLeaf
2017-05-25 15:59 31楼
AVL树通过留名
感谢神犇@cstdio ,感谢你的代码助我改对了rank()
GravatarHzoi_
2016-07-20 11:07 32楼
GravatarAntiLeaf
2017-05-25 16:03 33楼
Gravatar安呐一条小咸鱼。
2016-08-14 16:05 34楼
Splay总是打错......自己还是弱啊......
SBT打错......Splay大法好退Treap,SBT保平安
GravatarAntiLeaf
2016-09-15 14:35 35楼
Gravatar‎MistyEye
2016-10-01 19:01 36楼
用set过了5个点,T了五个点
GravatarHzoi_Go灬Fire
2016-10-06 21:10 37楼
新技能
替罪羊树 get√
GravatarAntiLeaf
2016-10-07 05:56 38楼
新技能
跳表 throw√
跳表不如STL
GravatarYGOI_真神名曰驴蛋蛋
2016-10-12 08:23 39楼
回复 @Asm.Def :
又TMD是神秘的Linux关键字 (╯‵□′)╯︵┻━┻
多谢大神提醒
Gravatarcdcq
2016-10-22 09:32 40楼
优美的SBT代码
GravatarGo灬Fire
2017-04-16 17:56 41楼
少一个pushup调了一小时
GravatarGo灬Fire
2016-12-11 19:42 42楼
拿线段树A了
Gravatarsxysxy
2016-12-15 17:28 43楼
第1K次提交记录
GravatarYGOI_真神名曰驴蛋蛋
2017-01-02 14:50 44楼
GravatarSky_miner
2017-01-15 08:25 45楼
GravatarL_in
2017-02-20 18:56 46楼
01Trie用结构体包起来也只写了46行//id=364857
Gravatar_Itachi
2017-01-19 21:45 47楼
Gravatar半汪
2017-02-21 08:16 48楼
GravatarGo灬Fire
2017-04-20 16:44 49楼
GravatarL_in
2017-03-13 15:40 50楼
比楼上上优美的Treap
Gravatar可以的.
2017-04-16 17:52 51楼
好吧我承认我当时的treap世界第二zz,仅次于ls
GravatarGo灬Fire
2017-04-16 17:59 52楼
反人类的数组Treap不反人类的指针TreapSplay
SBT替罪羊树01Trie,无旋Treap
然后究竟为什么数组这么快啊(╯‵□′)╯︵┻━┻
GravatarHZOI_蒟蒻一只
2017-07-12 20:28 53楼
第一发平衡树 Treap!!
GravatarkZime
2017-06-10 10:21 54楼
Treap首题留念
板子真难打= =
GravatarHzoi_Mafia
2017-07-25 13:00 55楼
treap 2站
有人介绍一下数组treap和指针treap的差异和优缺点吗
我就会数组的。。。。
Gravatar하루Kiev
2017-07-12 16:19 56楼
回复 @하루Kiev : 省内存啊……
GravatarHZOI_蒟蒻一只
2017-07-12 16:47 57楼
实在闲的无聊写了一下红黑树。。。感觉自己萌萌的
GravatarZlycerQan
2017-08-13 09:39 58楼
treap真难调。。。
Gravatarxzz_233
2017-07-30 18:32 59楼
当真把maintain改成Maintain就过了。
Gravatarjoel
2017-07-31 15:56 60楼
splay
Gravatarhunter
2017-08-02 20:48 61楼
回复 @하루Kiev : 看脸
GravatarHzoi_Ivan
2017-08-03 11:48 62楼
01Trie
GravatarCooook
2017-08-03 15:39 63楼
第一发treap
GravatarJustWB
2017-08-31 13:57 64楼
对着模板只要有一点不一样就又w又t,我还是太垃圾了
GravatarHyoi_Turkey
2017-09-08 14:58 65楼
用线段树写的平衡树,离散化记得判重.
GravatarFisher.
2017-10-13 15:41 66楼
yeah
treap首题
GravatarHyoi_Turkey
2017-12-10 11:10 67楼
又复习了一下板子1a辣
GravatarHyoi_Turkey
2017-12-11 19:37 68楼
漏洞百出的splay
GravatarHyoi_Turkey
2017-12-16 19:24 69楼
膜拜神犇Lazer
扑通扑通跪下来Orz
GravatarHzoi_Ivan
2017-12-25 21:04 70楼
强烈抗议 Lazer2001 的刷榜行为。
GravatarWildRage
2017-12-26 15:37 71楼
回复 @hzoi_WildRage :
我觉得一年之内不会有人上榜……
GravatarLazer2001
2017-12-26 15:38 72楼
treap好短啊
Gravatarhyghb
2018-01-07 19:51 73楼
01trie好短
Gravatarhyghb
2018-01-17 17:27 74楼
原来爆零竟是因为maintain()。。好鬼畜的评测机呦。。。
UPD::然而又写了个Splay,爆零后把函数名全部改了一遍,还是爆零。最后fa♂现是freopen()被注释了。。
Gravatar_WA自动机
2018-02-17 22:50 75楼
90分的代码调了一天,mk学长指教过后总算知道了是右区间小于左区间导致死循环......
Gravatarサイタマ
2018-04-14 20:22 76楼
FHQ_treap好写又好调,强推,还资瓷可持久化 qwq
GravatarHale
2019-07-17 22:18 77楼
吹爆平板电视
Gravatar雾茗
2019-08-09 10:31 78楼

1829. [Tyvj 1728]普通平衡树

★★★   输入文件:phs.in   输出文件:phs.out   简单对比
时间限制:1 s   内存限制:1000 MB

【题目描述】

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

【输入格式】

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

【输出格式】

对于操作3,4,5,6每行输出一个数,表示对应答案

【样例输入】

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

【样例输出】

106465
84185
492737

【提示】

1.n的数据范围:n<=100000

2.每个数的数据范围:[-1e7,1e7]