。。也没什么好说的了，《Size Balanced Tree》（CQF WC 2006）说的很清楚了……
今晚（昨晚？手敲的代码……不知道如何……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> #include<queue> #define L(x) T[(x)].ls #define Ln(x) T[T[(x)].ls] #define R(x) T[(x)].rs #define Rn(x) T[T[(x)].ls] #define W(x) T[(x)].w #define S(x) T[(x)].size using namespace std; const int MAXN=100000; const int INF=2147483647; int root=0; struct Node{ int ls,rs,size,w; Node():ls(0),rs(0),size(0),w(0){} }; Node T[MAXN]; int sz,n; void RR(int &s){ int x = s; int k=L(s); L(s)=R(k); R(k)=s; S(k)=S(s); S(s)=S(L(s))+S(R(s))+1; s = k; } void LR(int &s){ int x = s; int k=R(s); R(s)=L(k); L(k)=s; S(k)=S(s); S(s)=S(L(s))+S(R(s))+1; s = k; } void Maintain(int &s,bool op){ if (s == 0)return; if(!op){ if( S(R(s)) < S(L(L(s))) )RR(s); else if( S(R(s)) < S(R(L(s))) ){ LR(L(s));RR(s); } else return; }else{ if( S(L(s)) < S(R(R(s))) )LR(s); else if( S(L(s)) < S(L(R(s))) ){ RR(R(s));LR(s); } else return; } Maintain(L(s),false); Maintain(R(s),true); Maintain(s,false); Maintain(s,true); } void Insert(int &s,int val){ if(s==0){ s=++sz;S(s)++;W(s)=val;return; } S(s)++; if(W(s)>val)Insert(L(s),val); else Insert(R(s),val); Maintain(s,(val>=W(s))); } int Delete(int &s,int v){ S(s)--; if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){ int ans=W(s); if(!(L(s)*R(s))){ s=L(s)+R(s); }else{ W(s)=Delete(L(s),W(s)+1); } return ans; }else{ if(W(s)>v) return Delete(L(s),v); else return Delete(R(s),v); } } int Search(int &s,int v){ if(!s)return INF; if(v==W(s))return s; else if(W(s)>v) return Search(L(s),v); else return Search(R(s),v); } int Select(int &s,int k){ if(k>S(root)) return INF; int Lt=S(L(s)); if(k==Lt) return W(s); else if(Lt>k) return Select(L(s),k); else return Select(R(s),k-Lt-1); } int Rank(int &s,int x){ if(!s)return INF; int Lt=S(L(s)); if(x==W(s))return Lt; else if(W(s)>x)return Rank(L(s),x); else return Rank(R(s),x)+Lt+1; } int main(){ int c; int x; while(cin>>c>>x){ switch(c){ case 0:Insert(root,x);break; case 1:Delete(root,x);break; case 2:cout<<Search(root,x)<<endl;break; case 3:cout<<Select(root,x)<<endl;break; case 4:cout<<Rank(root,x)<<endl;break; default:cout<<endl; } } return 0; } |
[Dr.Lib]Note:Data Structures – Size Balanced Tree – II by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.