[模板] Treap
2024-08-29 21:50:01
- 插入x
- 删除x
- 查询排名为x的数
- 查询x的排名
- 求x的前驱、后继
//Stay foolish,stay hungry,stay young,stay simple
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
using namespace std;
const int MAXN=100010;
const int INF=1<<29;
int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c)){
ret=ret*10+c-'0';
c=getchar();
}
return ret*f;
}
struct Treap{
int l,r;
int val,dat;
int cnt,size;
}node[MAXN];
int tcnt,root,n;
int add(int val){
node[++tcnt].val = val;
node[tcnt].dat = rand();
node[tcnt].cnt = node[tcnt].size = 1;
return tcnt;
}
void updata(int x){
node[x].size =node[node[x].l].size+node[node[x].r].size+node[x].cnt;
}
void build(){
add(-INF);add(INF);
root=1;node[1].r=2;
updata(root);
}
int GetRankByVal(int x,int val){
if(x==0) return 0;
if(val==node[x].val) return node[node[x].l].size+1;
if(val<node[x].val) return GetRankByVal(node[x].l,val);
return GetRankByVal(node[x].r,val)+node[node[x].l].size+node[x].cnt;
}
int GetValByRank(int x,int rank){
if(x==0) return INF;
if(node[node[x].l].size>=rank) return GetValByRank(node[x].l,rank);
if(node[node[x].l].size+node[x].cnt>=rank) return node[x].val;
return GetValByRank(node[x].r,rank-node[node[x].l].size-node[x].cnt);
}
void zig(int &x){
int y=node[x].l;
node[x].l=node[y].r;node[y].r=x;x=y;
updata(node[x].r);updata(x);
}
void zag(int &x){
int y=node[x].r;
node[x].r = node[y].l;node[y].l = x;x=y;
updata(node[x].l);updata(x);
}
void inst(int &x,int val){
if(x==0){
x=add(val);
return;
}
if(val==node[x].val){
node[x].cnt++;
updata(x);
return;
}
if(val<node[x].val){
inst(node[x].l,val);
if(node[x].dat<node[node[x].l].dat) zig(x);
}else{
inst(node[x].r,val);
if(node[x].dat<node[node[x].r].dat) zag(x);
}
updata(x);
}
int GetPre(int val){
int ans=1;
int x=root;
while(x){
if(val==node[x].val){
if(node[x].l>0){
x=node[x].l;
while(node[x].r>0) x=node[x].r;
ans=x;
}
break;
}
if(node[x].val<val&&node[x].val>node[ans].val) ans=x;
x=val<node[x].val?node[x].l:node[x].r;
}
return node[ans].val;//ans
}
int GetNext(int val){
int ans=2;
int x=root;
while(x){
if(val==node[x].val){
if(node[x].r>0){
x=node[x].r;
while(node[x].l>0) x=node[x].l;
ans=x;
}
break;
}
if(node[x].val>val&&node[x].val<node[ans].val) ans=x;
x=val<node[x].val?node[x].l:node[x].r;
}
return node[ans].val;
}
void remove(int &x,int val){
if(x==0) return;
if(val==node[x].val){
if(node[x].cnt>1){
node[x].cnt--;updata(x);
return;
}
if(node[x].l||node[x].r){
if(node[x].r==0||node[node[x].l].dat>node[node[x].r].dat){
zig(x),remove(node[x].r,val);
}else{
zag(x),remove(node[x].l,val);
}
updata(x);
}
else x=0;
return;
}
val<node[x].val?remove(node[x].l,val):remove(node[x].r,val);
updata(x);
}
int main(){
n=rd();
build();
while(n--){
int opt,x;
opt=rd();x=rd();
switch(opt){
case 1:
inst(root,x);
break;
case 2:
remove(root,x);
break;
case 3:
printf("%d\n",GetRankByVal(root,x)-1);
break;
case 4:
printf("%d\n",GetValByRank(root,x+1));
break;
case 5:
printf("%d\n",GetPre(x));
break;
case 6:
printf("%d\n",GetNext(x));
break;
}
}
return 0;
}
最新文章
- 报错注入分析之Extractvalue分析
- C# 定时器 Timers.Timer Forms.Timer
- GIS管网项目-flex/java
- Android中什么时候使用get和post 以及他们的优缺点！！
- MySQL服务 - 客户端工具mysql及mysqladmin使用介绍
- CSS文件开头到底声明@charset "utf-8"
- Delphi公司的生存哲学
- 文件夹oradiag_是如何产生的
- https加密
- vs2013 JS代码提示
- ESP8266学习笔记1：怎样在安信可全功能測试板上实现ESP-01的编译下载和调试
- 深入理解Java虚拟机--上
- lambda函数式编程
- OAuth2.0原理与实现
- 构建之法——Team & Scrum & MSF
- Java中的null
- flask中的if __name__ == "__main__"
- python之冒泡排序
- 将已有的项目提交到GitHub
- bzoj4144【AMPPZ2014】Petrol