FHQ Treap 详解( 二 ) _生活百科

具体的还是看代码吧。

代码

#include <bits/stdc++.h>#define TIME 1e3*clock()/CLOCKS_PER_SECusing namespace std;// stay organizedmt19937 rnd(233);const int maxn=1e5+10;struct Node{int ls,rs;int siz;int val,key;}tree[maxn];int rt=0,tot=0;int newnode(int val){tot++;tree[tot].ls=tree[tot].rs=0;tree[tot].siz=1;tree[tot].val=val;tree[tot].key=rnd();return tot;}void upd(int x){tree[x].siz=tree[tree[x].ls].siz+1+tree[tree[x].rs].siz;}void split(int cur,int k,int &x,int &y){if(!cur){x=y=0;return;}if(tree[cur].val<=k){x=cur;split(tree[x].rs,k,tree[x].rs,y);}else{y=cur;split(tree[y].ls,k,x,tree[y].ls);}upd(cur);}int merge(int x,int y){if(!x||!y)return x+y;if(tree[x].key>=tree[y].key){tree[x].rs=merge(tree[x].rs,y);upd(x);return x;}else{tree[y].ls=merge(x,tree[y].ls);upd(y);return y;}}int x,y,z;void ins(int val){split(rt,val,x,y);rt=merge(merge(x,newnode(val)),y);}void del(int val){split(rt,val-1,x,y);split(y,val,y,z);y=merge(tree[y].ls,tree[y].rs);rt=merge(merge(x,y),z);}int rnk(int val){split(rt,val-1,x,y);int ans=tree[x].siz+1;rt=merge(x,y);return ans;}int kth(int now,int k){while(tree[tree[now].ls].siz+1!=k){if(tree[tree[now].ls].siz+1>k)now=tree[now].ls;else{k-=tree[tree[now].ls].siz+1;now=tree[now].rs;}}return tree[now].val;}int pre(int val){split(rt,val-1,x,y);int ans=kth(x,tree[x].siz);rt=merge(x,y);return ans;}int suf(int val){split(rt,val,x,y);int ans=kth(y,1);rt=merge(x,y);return ans;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;int opt,x;while(t--){cin>>opt>>x;if(opt==1)ins(x);else if(opt==2)del(x);else if(opt==3)cout<<rnk(x)<<'\n';else if(opt==4)cout<<kth(rt,x)<<'\n';else if(opt==5)cout<<pre(x)<<'\n';else cout<<suf(x)<<'\n';}return 0;// you should actually read the stuff at the bottom}/* stuff you should look for* int overflow, array bounds* clear the arrays?* special cases (n=1?),* WRITE STUFF DOWN,* DON'T GET STUCK ON ONE APPROACH*/

完结撒花 owo~

FHQ Treap 详解( 二 )

推荐阅读

伶人是男是女

2020疫情期间蓝梦海洋王国开园时间

崂山特产都有什么，青岛崂山的特产与介绍

炒茄子怎么做好吃窍门炒茄子怎么做好吃窍门图片

古风诗意的句子古风诗意的句子是什么

观香看事可信吗观香是什么意思

新宝马5果断黑色宝马5系黑色

让天蝎男疯狂的水瓶女天蝎男一生难忘的水瓶女

客来福衣柜与好莱客衣柜哪个质量好好莱客衣柜怎么样

健康平安的名字新生儿取名方法

钟原赵欣是什么电视剧啊钟原赵欣是什么电视剧啊?

男女初次见面送的花第一次约会送什么礼物好

天天酷跑五星宠物哪个比较好一些[多图]

铁锈水滴在车上怎么洗锈水滴在车上怎么清洗

四大民间故事分别指什么

长沙市毕业生档案存放地址长沙高校毕业生档案信息查询指南

铁线莲的种子播种 * 和注意事项铁线莲种子播种前的处理 *

苹果13激活时间查看技巧苹果如何查询手机激活时间

2021一2022女排超级联赛时间表 2021一2022女排超级联赛时间

小伤痕容易导致车体生锈车身容易生锈