P3369 【模板】普通平衡树(Treap/SBT)(pb_ds版)
2024-08-31 13:04:57
题目描述
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
插入x数
删除x数(若有多个相同的数,因只删除一个)
查询x数的排名(若有多个相同的数,因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x,且最大的数)
- 求x的后继(后继定义为大于x,且最小的数)
输入输出格式
输入格式:
第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)
输出格式:
对于操作3,4,5,6每行输出一个数,表示对应答案
输入输出样例
输入样例#1:
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出样例#1:
106465
84185
492737
说明
时空限制:1000ms,128M
1.n的数据范围:n<=100000
2.每个数的数据范围:[-1e7,1e7]
来源:Tyvj1728 原名:普通平衡树
在此鸣谢
颓废的时候闲来无事研究一下pb_ds,,
想象一下在考场上别人花n个小时写平衡树调平衡树,而你五分钟就秒了的快感
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<algorithm>
#define lli long long
using namespace std;
using namespace __gnu_pbds;
void read(lli &n)
{
char c='+';lli x=;bool flag=;
while(c<''||c>''){c=getchar();if(c=='-')flag=;}
while(c>=''&&c<=''){x=x*+(c-);c=getchar();}
flag==?n=-x:n=x;
}
tree<lli,null_type,std::less<lli>,splay_tree_tag,tree_order_statistics_node_update>st;
int main()
{
ios::sync_with_stdio();
lli T;
lli ans,x,y;
cin>>T;
for(lli i=;i<=T;i++)
{ //read(x);read(y);
cin>>x>>y;
if(x==) st.insert((y<<)+i);
else if(x==)st.erase(st.lower_bound(y<<));
else if(x==)printf("%lld\n",st.order_of_key(y<<)+);
else
{
if(x==)ans=*st.find_by_order(y-);
if(x==)ans=*--st.lower_bound(y<<);
if(x==)ans=*st.lower_bound((y+)<<);
printf("%lld\n",ans>>);
}
}
return ;
}
最新文章
- Select标签下拉列表二级联动级联
- ubuntu15.04安装Chrome浏览器
- Nexus私服忘记用户名密码,Nexus私服如何找回用户名密码
- ITIL图示
- IIS与Apache共用80端口方法[试用成功]
- 使用Axure制作App原型应该怎样设置尺寸?
- CSS 去掉IE10中type=password中的眼睛图标
- Web Service学习笔记
- [DEncrypt] HashEncode--哈希加密帮助类 (转载)
- 转:char*, char[] ,CString, string的转换
- file_get_contents()的另一种使用方法
- POJ 1721 CARDS(置换群)
- VS 2017开发ASP.NET Core Web应用过程中发现的一个重大Bug
- Python教程(2.7)——条件分支
- docker:(3)docker容器挂载宿主主机目录
- opencv学习之路(40)、人脸识别算法——EigenFace、FisherFace、LBPH
- C#设计模式之10:状态模式
- EF Codefirst入门之创建数据库
- P1438 无聊的数列
- 跟我学Spring Boot(一)创建Spring Boot 项目