1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define N 100005 6 using namespace std; 7 struct SBT{ 8 // 左子树指针，右子树指针，大小，键值 9 int left,right,size,key; 10 void Init(){ 11 left=right=key= 0; 12 size= 1; 13 } 14 }T[N]; 15 int root,tot; // 根的位置以及节点个数 16 // 左旋转处理 17 void Left_rot( int &x){ 18 int k=T[x].right; 19 T[x].right=T[k].left; 20 T[k].left=x; 21 T[k].size=T[x].size; 22 T[x].size=T[T[x].left].size+T[T[x].right].size+ 1; 23 x=k; 24 } 25 // 右旋转处理 26 void Right_rot( int &x){ 27 int k=T[x].left; 28 T[x].left=T[k].right; 29 T[k].right=x; 30 T[k].size=T[x].size; 31 T[x].size=T[T[x].left].size+T[T[x].right].size+ 1; 32 x=k; 33 } 34 // 调整处理 35 void Maintain( int &r, bool flag){ 36 if(flag){ // 更新右子树 37 if(T[T[T[r].right].right].size>T[T[r].left].size) 38 Left_rot(r); 39 else if(T[T[T[r].right].left].size>T[T[r].left].size){ 40 Right_rot(T[r].right); 41 Left_rot(r); 42 } 43 else 44 return; 45 } 46 else{ // 更新在左子树 47 if(T[T[T[r].left].left].size>T[T[r].right].size) 48 Right_rot(r); 49 else if(T[T[T[r].left].right].size>T[T[r].right].size){ 50 Left_rot(T[r].left); 51 Right_rot(r); 52 } 53 else 54 return; 55 } 56 // 更新子树，然后再更新根，直到平衡为止 57 Maintain(T[r].left, false); 58 Maintain(T[r].right, true); 59 Maintain(r, false); 60 Maintain(r, true); 61 } 62 // 插入新节点 63 void Insert( int &r, int k){ 64 if(r== 0){ 65 r=++tot; 66 T[r].Init(); 67 T[r].key=k; 68 } 69 else{ 70 T[r].size++; 71 if(k<T[r].key) 72 Insert(T[r].left,k); 73 else 74 Insert(T[r].right,k); 75 // 插入后要调整，保证平衡 76 Maintain(r,k>=T[r].key); 77 } 78 } 79 // 删除结点，利用的是前驱替换 80 int Remove( int &r, int k){ 81 int d_key; 82 if(!r) 83 return 0; 84 T[r].size--; 85 // 前者说明就是要删的节点，后两者说明不存在此节点 86 if(T[r].key==k||(T[r].left== 0&&k<T[r].key)||(T[r].right== 0&&k>T[r].key)){ 87 d_key=T[r].key; 88 if(T[r].left&&T[r].right) 89 T[r].key=Remove(T[r].left,k+ 1); 90 else 91 r=T[r].left+T[r].right; 92 } 93 else Remove(k<T[r].key?T[r].left:T[r].right,k); 94 } 95 void Delete( int &r, int delay, int min_val){ 96 if(!r) return; 97 if(T[r].key+delay<min_val) { 98 r=T[r].right; 99 Delete(r,delay,min_val); 100 } 101 else{ 102 Delete(T[r].left,delay,min_val); 103 T[r].size=T[T[r].right].size+T[T[r].left].size+ 1; 104 } 105 } 106 // 取得最大值，即一直遍历到最右的结点 107 int Get_Max( int &r){ 108 while(T[r].right) 109 r=T[r].right; 110 return r; 111 } 112 // 取得最小值，即一直遍历到最左的结点 113 int Get_Min( int &r){ 114 while(T[r].left) 115 r=T[r].left; 116 return r; 117 } 118 // 获得前驱 119 int Get_Pre( int &r, int y, int k){ 120 if(r== 0) return y; 121 if(k>T[r].key) 122 Get_Pre(T[r].right,r,k); 123 else 124 Get_Pre(T[r].left,y,k); 125 } 126 // 获得后继 127 int Get_Next( int &r, int y, int k){ 128 if(r== 0) return y; 129 if(k<T[r].key) 130 Get_Next(T[r].left,r,k); 131 else 132 Get_Next(T[r].right,y,k); 133 } 134 // 取得第K小的数，注：暂不能解决有重复数的 135 int Get_Min_Kth( int &r, int k){ 136 int t=T[T[r].left].size+ 1; 137 if(t==k) return T[r].key; 138 if(t<k) return Get_Min_Kth(T[r].right,k-r); 139 else return Get_Min_Kth(T[r].left,k); 140 } 141 // 取得第K大的数 142 int Get_Max_Kth( int &r, int k){ 143 int t=T[T[r].right].size+ 1; 144 if(t==k) return T[r].key; 145 if(t<k) return Get_Max_Kth(T[r].left,k-t); 146 else return Get_Max_Kth(T[r].right,k); 147 } 148 // 获得结点的名次 149 int Get_Rank( int &r, int k){ 150 if(k<T[r].key) 151 return Get_Rank(T[r].left,k); 152 else if(k>T[r].key) 153 return Get_Rank(T[r].right,k)+T[T[r].left].size+ 1; 154 else 155 return T[T[r].left].size+ 1; 156 } 157 // 排序 158 void Inorder( int &r){ 159 if(r== 0) return; 160 Inorder(T[r].left); 161 printf( " %d\n ",T[r].key); 162 Inorder(T[r].right); 163 }