| 题目名称 | 1594. [TYVJ1730]二逼平衡树 |
|---|---|
| 输入输出 | psh.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 OI永别
于2014-04-15加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：224， 提交：698， 通过率：32.09% | ||||
 Cydiater |
100 | 0.605 s | 59.83 MiB | C++ |
|
Cydiater |
100 | 0.612 s | 290.62 MiB | C++ |
|
Go灬Fire |
100 | 0.618 s | 348.80 MiB | C++ |
|
Go灬Fire |
100 | 0.622 s | 348.80 MiB | C++ |
|
Go灬Fire |
100 | 0.659 s | 349.22 MiB | C++ |
|
Go灬Fire |
100 | 0.686 s | 262.38 MiB | C++ |
|
Cydiater |
100 | 0.708 s | 59.83 MiB | C++ |
|
Go灬Fire |
100 | 0.765 s | 288.59 MiB | C++ |
|
Cydiater |
100 | 0.787 s | 39.61 MiB | C++ |
 Anson |
100 | 0.801 s | 26.80 MiB | C++ |
| 本题关联比赛 | |||
| 清华集训2017模板练习 | |||
| 关于 二逼平衡树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
更靠谱的写法
| ||||
|
写了一天，终于啃下来了FHQ_treap套ST，qwq
| ||||
|
splay好奇怪啊...
insert没写splay比写了还快  hyghb
2018-01-06 11:05
27楼
| ||||
|
终于知道为何叫二逼平衡树了
打完整个人都二逼了= = | ||||
|
数组开小调了两天日啊，，，
在别的OJ都T，就cogs上A。。。 | ||||
|
| ||||
|
| ||||
|
你们一个个怎么都跑的那么快。。。。
简直残暴。。。 | ||||
 HZOI_蒟蒻一只
2017-04-30 16:10
20楼
| ||||
瑆の時間~無盡輪迴·林蔭
Hale
xzz_666
Hzoi_Mafia
wumingshi
Hzoi_Ivan
Cooook
ZlycerQan【题目描述】
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
【输入格式】
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继
【输出格式】
对于操作1,2,4,5各输出一行，表示查询结果
【样例输入】
9 6 4 2 2 1 9 4 0 1 1 2 1 4 3 3 4 10 2 1 4 3 1 2 5 9 4 3 9 5 5 2 8 5
【样例输出】
2 4 3 4 9
【提示】
n,m<=50000 保证有序序列所有值在任何时刻满足[0,10^8]但是询问的数未必
【来源】
tyvj1730