Tyvj 1728 普通平衡樹

?HYSBZ - 3224?

您需要寫一種數(shù)據(jù)結(jié)構(gòu)（可參考題目標(biāo)題），來維護(hù)一些數(shù)，其中需要提供以下操作：
1. 插入x數(shù)
2. 刪除x數(shù)(若有多個相同的數(shù)，因只刪除一個)
3. 查詢x數(shù)的排名(若有多個相同的數(shù)，因輸出最小的排名)
4. 查詢排名為x的數(shù)
5. 求x的前驅(qū)(前驅(qū)定義為小于x，且最大的數(shù))
6. 求x的后繼(后繼定義為大于x，且最小的數(shù))

Input

第一行為n，表示操作的個數(shù),下面n行每行有兩個數(shù)opt和x，opt表示操作的序號(1<=opt<=6)

Output

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

Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Output
106465
84185
492737

Hint?

1.n的數(shù)據(jù)范圍：n<=100000 2.每個數(shù)的數(shù)據(jù)范圍：[-2e9,2e9] sol：留了很久的巨坑終于嘗試著來填了。 推薦一篇講的很好blog但是代碼不可看的教程(保證學(xué)會) 自己的模板，代碼中有詳細(xì)的注釋，可配合上面的教程閱讀，體驗感極差 #include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() {ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-'); ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) {if(x<0){putchar('-'); x=-x;}if(x<10){putchar(x+'0'); return;}write(x/10);putchar((x%10)+'0');return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') const int N=200005,inf=0x3f3f3f3f; int n; namespace Pht {int Points; //總的節(jié)點數(shù)(重復(fù)元素算一個) int Root; //根節(jié)點 int Child[N][2]; //左\右兒子int Parent[N]; //父親int Cnt[N]; //這個節(jié)點的元素個數(shù)int Quanzhi[N]; //這個點的權(quán)值int Size[N]; //這棵字?jǐn)?shù)的元素個數(shù) inline void Init();inline int Check(int x);inline void PushUp(int x);inline void Rotate(int x);inline void Splay(int x);inline void Insert(int x);inline void Remove(int x);inline void Find(int x);inline int Ask_Lower(int x);inline int Ask_Upper(int x);inline int Ask_Kth(int x);inline void Init(){Points=Root=0;Insert(inf);Insert(-inf);return;}inline int Check(int x)//查詢這個節(jié)點是左\右兒子 {return (Child[Parent[x]][0]==x)?0:1;}inline void PushUp(int x)//跟新子樹中的元素個數(shù) {Size[x]=Cnt[x]+Size[Child[x][0]]+Size[Child[x][1]];return;}inline void Rotate(int x){int y,z,oo;y=Parent[x];z=Parent[y];oo=Check(x); //查詢x是左\右兒子 Child[y][oo]=Child[x][oo^1]; Parent[Child[x][oo^1]]=y; //把x的另一個子樹連給父親 Child[z][Check(y)]=x; Parent[x]=z; //x連給爺爺 Child[x][oo^1]=y; Parent[y]=x; //父親連給x PushUp(x); PushUp(y); //跟新子樹元素個數(shù) }inline void Splay(int At,int To)//把At轉(zhuǎn)到To {while(Parent[At]!=To){int Father=Parent[At];if(Parent[Father]==To)//當(dāng)前節(jié)點的爺爺已經(jīng)是To了 {Rotate(At);}else if(Check(At)==Check(Father)) //在一條連線上時雙旋 {Rotate(Father); Rotate(At);}else{Rotate(At); Rotate(At); //否則單旋*2 }}if(To==0) Root=At;//之前一直理解不了(我也不知道為什么),TMD轉(zhuǎn)到0節(jié)點下面了當(dāng)然就是根了啊 }inline void Insert(int Val) //插入權(quán)值為Val的節(jié)點 {int Now=Root,Par=0;while(Now&&Quanzhi[Now]!=Val){Par=Now;Now=Child[Now][(Val>Quanzhi[Now])?1:0];}if(Now) //已經(jīng)有這個權(quán)值了 {Cnt[Now]++; Size[Now]++;}else //沒有這個權(quán)值就新建一個節(jié)點 {Now=++Points;if(Par){Child[Par][(Val>Quanzhi[Par])?1:0]=Now;}Child[Now][0]=Child[Now][1]=0;Parent[Now]=Par;Quanzhi[Now]=Val;Cnt[Now]=Size[Now]=1;}Splay(Now,0); //每次插入都要轉(zhuǎn)到根,可以防止被卡Treturn;}inline void Remove(int Val) //刪除權(quán)值為Val的節(jié)點 {int Lower=Ask_Lower(Val),Upper=Ask_Upper(Val);Splay(Lower,0);Splay(Upper,Lower);int Pos=Child[Upper][0];//Lower比Val小,所以Lower轉(zhuǎn)上去后Val是Lower的右二子,再把Upper轉(zhuǎn)到Lower上,Val肯定就是Upper的左兒子了 if(Cnt[Pos]>1){Cnt[Pos]--; //有多個數(shù)字Splay(Pos,0);}else Child[Upper][0]=0;}inline void Find(int Val) //尋找權(quán)值為Val的節(jié)點的位置 {int Now=Root;if(!Root) return;//不能找 while(Child[Now][(Val>Quanzhi[Now])?1:0]&&(Val!=Quanzhi[Now]))//找權(quán)值Val的位置 {Now=Child[Now][(Val>Quanzhi[Now])?1:0];}Splay(Now,0);}inline int Ask_Lower(int Val)//查詢權(quán)值為Val的節(jié)點的前驅(qū) {Find(Val);int Now=Root;if(Quanzhi[Now]<Val) return Now;Now=Child[Now][0];while(Child[Now][1]) Now=Child[Now][1];return Now;}inline int Ask_Upper(int Val)//查詢權(quán)值為Val的節(jié)點的后繼 {Find(Val);int Now=Root;if(Quanzhi[Now]>Val) return Now;Now=Child[Now][1];while(Child[Now][0]) Now=Child[Now][0];return Now;}inline int Ask_Kth(int Id)//查詢第k大的數(shù) {int Now=Root;if(Size[Now]<Id) return 0;for(;;)//查詢第k大的數(shù),挺像主席樹的 {if(Id>Size[Child[Now][0]]+Cnt[Now]){Id-=Size[Child[Now][0]]+Cnt[Now];Now=Child[Now][1];}else if(Size[Child[Now][0]]>=Id) Now=Child[Now][0];else return Quanzhi[Now];}} } int main() {R(n);Pht::Init();while(n--){int opt=read(),x=read();switch (opt){case 1:Pht::Insert(x);break;case 2:Pht::Remove(x);break;case 3:Pht::Find(x);Wl(Pht::Size[Pht::Child[Pht::Root][0]]+1-1);//加1是因為之前的都是比x小的,所以加1,但是一開始插入了一個-inf所以-1break;case 4:x++;//一開始有一個-inf Wl(Pht::Ask_Kth(x));break;case 5:Wl(Pht::Quanzhi[Pht::Ask_Lower(x)]);break;case 6:Wl(Pht::Quanzhi[Pht::Ask_Upper(x)]);break;}}return 0; } /* input 10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598 output 106465 84185 492737 */ View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/gaojunonly1/p/10660074.html

總結(jié)

以上是生活随笔為你收集整理的bzoj3224的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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