Description
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)
Input
第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数,表示对应答案
Sample Input
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
84185
492737
HINT
Source
Solution
哦,这道题几乎涵盖了treap所有操作。然后窝写挂了好~~~长时间
话说BZOJ1500窝是不是AC无望QAQ
#include <bits/stdc++.h>
using namespace std;
struct treap
{
int l, r, siz, key, val, pri;
}a[];
int root, ptot, ans; void push_up(int k)
{
a[k].siz = a[a[k].l].siz + a[a[k].r].siz + a[k].val;
} void lturn(int &k)
{
int tmp = a[k].r;
a[k].r = a[tmp].l, a[tmp].l = k;
a[tmp].siz = a[k].siz, push_up(k), k = tmp;
} void rturn(int &k)
{
int tmp = a[k].l;
a[k].l = a[tmp].r, a[tmp].r = k;
a[tmp].siz = a[k].siz, push_up(k), k = tmp;
} void insert(int &k, int x)
{
if(!k)
{
k = ++ptot, a[k].siz = a[k].val = ;
a[k].key = x, a[k].pri = rand();
return;
}
a[k].siz++;
if(x == a[k].key) a[k].val++;
else if(x < a[k].key)
{
insert(a[k].l, x);
if(a[k].pri < a[a[k].l].pri) rturn(k);
}
else
{
insert(a[k].r, x);
if(a[k].pri < a[a[k].r].pri) lturn(k);
}
} void del(int &k, int x)
{
if(!k) return;
if(x == a[k].key)
if(a[k].val > ) a[k].val--, a[k].siz--;
else if(!(a[k].l * a[k].r)) k = a[k].l + a[k].r;
else if(a[a[k].l].pri < a[a[k].r].pri)
lturn(k), del(k, x);
else rturn(k), del(k, x);
else if(x < a[k].key) a[k].siz--, del(a[k].l, x);
else a[k].siz--, del(a[k].r, x);
} int query_rank(int k, int x)
{
if(!k) return ;
if(x < a[k].key) return query_rank(a[k].l, x);
if(x == a[k].key) return a[a[k].l].siz + ;
return a[a[k].l].siz + a[k].val + query_rank(a[k].r, x);
} int query_num(int k, int x)
{
if(!k) return ;
if(x <= a[a[k].l].siz) return query_num(a[k].l, x);
if(x <= a[a[k].l].siz + a[k].val) return a[k].key;
return query_num(a[k].r, x - a[a[k].l].siz - a[k].val);
} void query_pro(int k, int x)
{
if(!k) return;
if(x <= a[k].key) query_pro(a[k].l, x);
else ans = a[k].key, query_pro(a[k].r, x);
} void query_sub(int k, int x)
{
if(!k) return;
if(x >= a[k].key) query_sub(a[k].r, x);
else ans = a[k].key, query_sub(a[k].l, x);
} int main()
{
int n, op, x;
scanf("%d", &n), srand(n);
while(n--)
{
scanf("%d%d", &op, &x);
if(op == ) insert(root, x);
if(op == ) del(root, x);
if(op == ) printf("%d\n", query_rank(root, x));
if(op == ) printf("%d\n", query_num(root, x));
if(op == ) ans = , query_pro(root, x), printf("%d\n", ans);
if(op == ) ans = , query_sub(root, x), printf("%d\n", ans);
}
return ;
}
[BZOJ3224] [Tyvj 1728] 普通平衡树 (treap)的更多相关文章
-
[BZOJ3224]Tyvj 1728 普通平衡树
[BZOJ3224]Tyvj 1728 普通平衡树 试题描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:1. 插入x数2. 删除x数(若有多个相同的数,因只删除一个) ...
-
bzoj3224: Tyvj 1728 普通平衡树(平衡树)
bzoj3224: Tyvj 1728 普通平衡树(平衡树) 总结 a. cout<<(x=3)<<endl;这句话输出的值是3,那么对应的,在splay操作中,当父亲不为0的 ...
-
BZOJ 3224 TYVJ 1728 普通平衡树 [Treap树模板]
3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 7390 Solved: 3122 [Submit][S ...
-
bzoj3224 Tyvj 1728 普通平衡树(名次树+处理相同)
3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 5354 Solved: 2196[Submit][Sta ...
-
BZOJ 3224: Tyvj 1728 普通平衡树 treap
3224: Tyvj 1728 普通平衡树 Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:1. 插入x数2. 删除x数(若有多个相同的数,因只删除 ...
-
bzoj3224: Tyvj 1728 普通平衡树(splay)
3224: Tyvj 1728 普通平衡树 题目:传送门 题解: 啦啦啦啦又来敲个模版水经验啦~ 代码: #include<cstdio> #include<cstring> ...
-
BZOJ3224 Tyvj 1728 普通平衡树(Treap)
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...
-
【权值线段树】bzoj3224 Tyvj 1728 普通平衡树
一个板子. #include<cstdio> #include<algorithm> using namespace std; #define N 100001 struct ...
-
BZOJ3224——Tyvj 1728 普通平衡树
1.题目大意:数据结构题,是treap,全都是treap比较基本的操作 2.分析:没啥思考的 #include <cstdio> #include <cstdlib> #inc ...
随机推荐
-
POJ 2075
#include<iostream> #include<stdio.h> #include<string> #include<map> #include ...
-
android 使用虚拟机安装apk(图文教程)(转)
1.启动虚拟机 2.我的android sdk在“E:\android\android开发环境\android SDK\platform-tools”把要安装的apk复制到这个根目录(和adb.exe ...
-
WCF服务的创建和发布到IIS
一. WCF服务的创建 有两种创建方式: 1.WCF服务库 2.WCF服务应用程序 如下图所示: 这里选择WCF服务库.注意事项: 1.WCF服务库是一个类库项目,这里选择.net 3.5版本(版本高 ...
-
php不同形式的实现a-z的26个字母的输出
直接上代码: for($i=ord('a'), $n=ord('z'); $i<=$n; $i++){ echo chr($i),PHP_EOL; } echo PHP_EOL; $char = ...
-
Tomcat 80 端口被占,解决方案
Windows 平台下Tomcat启动不起,显示 SEVERE: Failed to initialize end point associated with ProtocolHandler [&qu ...
-
node.js上除了Express还有哪些好用的web开发框架
老司机都有体会, 开发本身没有多难, 最纠结其实是最初的技术和框架选型, 本没有绝对的好坏之分, 可一旦选择了不适合于自己业务场景的框架, 将来木已成舟后开发和维护成本都很高, 等发现不合适的时候更换 ...
-
序列化与ArrayList 的elementData的修饰关键字transient
transient用来表示一个域不是该对象序行化的一部分,当一个对象被序行化的时候,transient修饰的变量不会被序列化 ArrayList的动态数组elementData被transient ...
-
busybox 安装问题解决
直接编译错误 1.loginutils/passwd.c:93:16: error: storage size of ‘rlimit_fsize’ isn’t known 解决方法:在busybox根 ...
-
学习C语言以及C语言基础调查
学习声乐的心得 你有什么技能比大多人(超过90%以上)更好? 就我个人而言,在所有的兴趣之中,做得比较好的应该属于声乐. 针对这个技能的获取你有什么成功的经验? 我对于声乐处始于兴趣,成功的经 ...
-
InnoDB锁问题
InnoDB锁问题 InnoDB与MyISAM的最大不同有两点:一是支持事务(TRANSACTION):二是采用了行级锁.行级锁与表级锁本来就有许多不同之处,另外,事务的引入也带来了一些新问题.下面我 ...