P3369 【模板】普通平衡树（TreapSBT）

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入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 原名：普通平衡树

在此鸣谢

平衡树裸题，不过对于萌新来说。啊啊啊啊啊

听说treap就是一棵二叉搜索树，不过有时他会退化为一条链，为了防止这一点，又虚拟了一个随机值，使这棵树满足堆的性质，如果操作时不满足了，就需要旋转（萌新不会啊）。

#include<iostream> #include<cstdlib> #include<cstdio> using namespace std; int n,root,cnt,ans; struct treap { int l,r,val,w,sz,rnd; }t[120005]; void update(int k) { t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].w; } void lt(int &k) { int now=t[k].r; t[k].r=t[now].l; t[now].l=k; t[now].sz=t[k].sz; update(k); k=now; } void rt(int &k) { int now=t[k].l; t[k].l=t[now].r; t[now].r=k; t[now].sz=t[k].sz; update(k); k=now; } void insert(int &k,int x) { if(k==0) { t[++cnt].val=x; t[cnt].sz=1; t[cnt].w=1; t[cnt].rnd=rand(); k=cnt; return ; } t[k].sz++; if(t[k].val==x) t[k].w++; else if(x>t[k].val) { insert(t[k].r,x); if(t[t[k].r].rnd<t[k].rnd) lt(k); } else { insert(t[k].l,x); if(t[t[k].l].rnd<t[k].rnd) rt(k); } } void del(int &k,int x) { if(k==0) return ; if(t[k].val==x) { if(t[k].w>1) { t[k].w--; t[k].sz--; return ; } if(t[k].l*t[k].r==0) k=t[k].l+t[k].r; else { if(t[t[k].l].rnd<t[t[k].r].rnd) { rt(k); del(k,x); } else { lt(k); del(k,x); } } return ; } t[k].sz--; if(x>t[k].val) del(t[k].r,x); if(x<t[k].val) del(t[k].l,x); } void ask_p(int k,int x,int mode) { if(mode==1) { if(!k) return ; if(t[k].val<x) { ans=t[k].val; ask_p(t[k].r,x,1); } else ask_p(t[k].l,x,1); } else { if(!k) return ; if(t[k].val>x) { ans=t[k].val; ask_p(t[k].l,x,2); } else ask_p(t[k].r,x,2); } } int ask_rank(int k,int x) { if(!k) return 0; if(t[k].val==x) return t[t[k].l].sz+1; if(t[k].val<x) return t[k].w+t[t[k].l].sz+ask_rank(t[k].r,x); return ask_rank(t[k].l,x); } int ask_num(int k,int x) { if(!k) return 0; if(x<=t[t[k].l].sz) return ask_num(t[k].l,x); if(x>t[t[k].l].sz+t[k].w) return ask_num(t[k].r,x-t[t[k].l].sz-t[k].w); return t[k].val; } int main() { scanf("%d",&n); while(n--) { int opt,x; scanf("%d%d",&opt,&x); switch(opt) { case 1: insert(root,x); break; case 2: del(root,x); break; case 3: printf("%d\n",ask_rank(root,x)); break; case 4: printf("%d\n",ask_num(root,x)); break; case 5: ask_p(root,x,1); printf("%d\n",ans); break; case 6: ask_p(root,x,2); printf("%d\n",ans); break; } } return 0; }