題目描述
您需要寫一種數(shù)據(jù)結(jié)構(gòu)（可參考題目標(biāo)題），來(lái)維護(hù)一些數(shù)，其中需要提供以下操作：

插入xx數(shù)
刪除xx數(shù)(若有多個(gè)相同的數(shù)，因只刪除一個(gè))
查詢xx數(shù)的排名(排名定義為比當(dāng)前數(shù)小的數(shù)的個(gè)數(shù)+1。若有多個(gè)相同的數(shù)，因輸出最小的排名)
查詢排名為xx的數(shù)
求xx的前驅(qū)(前驅(qū)定義為小于xx，且最大的數(shù))
求xx的后繼(后繼定義為大于xx，且最小的數(shù))
輸入格式
第一行為nn，表示操作的個(gè)數(shù),下面nn行每行有兩個(gè)數(shù)optopt和xx，optopt表示操作的序號(hào)$(1\le opt\le 6)$

輸出格式
對(duì)于操作3,4,5,6每行輸出一個(gè)數(shù)，表示對(duì)應(yīng)答案

輸入輸出樣例
輸入
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
輸出

106465
84185
492737

我終會(huì)寫一種平衡樹(shù)了，fhq treap 真的好寫啊，哈哈哈哈哈
代碼：

#include<stdio.h> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<vector> #include<cmath> #include<set> #include<map> #define ll long long #define INF 0x7f7f7f7f using namespace std; const int maxn=1e5+15; const int maxx=22000; struct FHQ {struct node{int son[2];int rnd,val,siz;}tr[maxn];int root;int tot;inline void update(int r){tr[r].siz=tr[tr[r].son[0]].siz+tr[tr[r].son[1]].siz+1;}void split(int r,int k,int &x,int &y){if(!r){x=y=0;return;}if(tr[r].val<=k){x=r;split(tr[r].son[1],k,tr[r].son[1],y);}else{y=r;split(tr[r].son[0],k,x,tr[r].son[0]);}update(r);}inline int merg(int x,int y){if(!x||!y)return x|y;if(tr[x].rnd<tr[y].rnd){tr[x].son[1]=merg(tr[x].son[1],y);update(x);return x;}else{tr[y].son[0]=merg(x,tr[y].son[0]);update(y);return y;}}inline int create(int val){tr[++tot].val=val;tr[tot].rnd=rand();tr[tot].siz=1;return tot;}int kth(int r,int k){for(;;){if(k<=tr[tr[r].son[0]].siz)r=tr[r].son[0];else{if(k==tr[tr[r].son[0]].siz+1)return tr[r].val;else{k-=tr[tr[r].son[0]].siz+1;r=tr[r].son[1];}}}}void inser(int val){int x,y;split(root,val,x,y);root=merg(merg(x,create(val)),y);}void del(int val){int x,y,z;split(root,val,x,z);split(x,val-1,x,y);y=merg(tr[y].son[0],tr[y].son[1]);root=merg(merg(x,y),z);}int getRank(int val){int x,y;split(root,val-1,x,y);int ans=tr[x].siz+1;root=merg(x,y);return ans;}int pre(int val){int x,y;split(root,val-1,x,y);int ans=kth(x,tr[x].siz);root=merg(x,y);return ans;}int nex(int val){int x,y;split(root,val,x,y);int ans=kth(y,1);root=merg(x,y);return ans;} }fhq; int main() {int n;cin>>n;int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(x==1)fhq.inser(y);else if(x==2)fhq.del(y);else if(x==3)printf("%d\n",fhq.getRank(y));else if(x==4)printf("%d\n",fhq.kth(fhq.root,y));else if(x==5)printf("%d\n",fhq.pre(y));else printf("%d\n",fhq.nex(y));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3369 【模板】普通平衡树(fhq treap)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。