ZOJ2112 Dynamic Rankings 動態區間第K最值 平方分割，zoj2112rankings
有了上一題的經驗（POJ的靜態區間第K最值）再解決這道題就輕松多了
空間5256KB，時間3330ms，如果把動態開點的平衡樹換成數組模擬的話應該會更快
之所以選擇了平方分割而不是樹套樹，不僅是所謂趁熱打鐵，更是因為：
平方分割的修改操作，無論編程復雜度還是時間復雜度都遠優於樹套樹。
代碼如下：（鄙人不才，不會壓代碼，所以寫了300多行Σ( ° △ °|||)
![]()
1 template <class T>
2 struct SbtNode
3 {
4 typedef SbtNode<T> Node;
5 Node* lch;
6 Node* rch;
7
8 T val;
9 int lSize;
10 int rSize;
11
12 SbtNode(const T& _val):
13 lch(0),rch(0),val(_val),lSize(0),rSize(0) {}
14 void assign(const T& _val)
15 {
16 lch=rch=0;
17 val=_val;
18 lSize=rSize=0;
19 }
20 };
21
22 template <class T,class Comp>
23 struct SizeBlcTree
24 {
25 enum { None=-1,Left=0,Right=1 };
26 typedef SbtNode<T> Node;
27 typedef SizeBlcTree<T,Comp> Sbt;
28
29 Node* root;
30 Comp cmp;
31
32 SizeBlcTree():root(0) {}
33 ~SizeBlcTree() { clear(); }
34
35 void clear_aux(Node* _cur)
36 {
37 if(_cur->lch) clear_aux(_cur->lch);
38 if(_cur->rch) clear_aux(_cur->rch);
39 delete _cur;
40 }
41
42 void clear()
43 {
44 if(root) clear_aux(root);
45 root=0;
46 }
47
48 Node* lRotate(Node* _cur)
49 {
50 Node* next=_cur->rch;
51 _cur->rch=next->lch;
52 next->lch=_cur;
53
54 _cur->rSize=next->lSize;
55 next->lSize+=(_cur->lSize+1);
56
57 return next;
58 }
59
60 Node* rRotate(Node* _cur)
61 {
62 Node* next=_cur->lch;
63 _cur->lch=next->rch;
64 next->rch=_cur;
65
66 _cur->lSize=next->rSize;
67 next->rSize+=(_cur->rSize+1);
68
69 return next;
70 }
71
72 Node* insert_aux(const T& _val,Node* _cur)
73 {
74 if(!_cur) return new Node(_val);
75
76 if(cmp(_val,_cur->val))
77 {
78 ++_cur->lSize;
79 _cur->lch=insert_aux(_val,_cur->lch);
80 if(_cur->lch->lSize > _cur->rSize) return rRotate(_cur);
81 else if(_cur->lch->rSize > _cur->rSize)
82 {
83 _cur->lch=lRotate(_cur->lch);
84 return rRotate(_cur);
85 }
86 else return _cur;
87 }
88 else
89 {
90 ++_cur->rSize;
91 _cur->rch=insert_aux(_val,_cur->rch);
92 if(_cur->rch->rSize > _cur->lSize) return lRotate(_cur);
93 else if(_cur->rch->lSize > _cur->lSize)
94 {
95 _cur->rch=rRotate(_cur->rch);
96 return lRotate(_cur);
97 }
98 else return _cur;
99 }
100 }
101
102 Sbt& operator << (const T& _val)
103 {
104 root=insert_aux(_val,root);
105 return *this;
106 }
107
108 Node* erase_aux(const T& _val,Node* _cur,bool& _found)
109 {
110 if(!_cur)
111 {
112 _found=false;
113 return 0;
114 }
115 if(cmp(_val,_cur->val))
116 {
117 _cur->lch=erase_aux(_val,_cur->lch,_found);
118 if(_found) --_cur->lSize;
119 return _cur;
120 }
121 if(cmp(_cur->val,_val))
122 {
123 _cur->rch=erase_aux(_val,_cur->rch,_found);
124 if(_found) --_cur->rSize;
125 return _cur;
126 }
127
128 _found=true;
129 int status=0;
130 if(_cur->lch) status|=1;
131 if(_cur->rch) status|=2;
132 Node* res;
133 Node* &prev=res;
134
135 switch(status)
136 {
137 case 0:
138 delete _cur;
139 return 0;
140 case 1:
141 res=_cur->lch;
142 delete _cur;
143 return res;
144 case 2:
145 res=_cur->rch;
146 delete _cur;
147 return res;
148 case 3:
149 prev=_cur;
150 if(prev->rch->lch)
151 {
152 --prev->rSize;
153 prev=prev->rch;
154
155 while(prev->lch->lch)
156 {
157 --prev->lSize;
158 prev=prev->lch;
159 }
160 _cur->val=prev->lch->val;
161 prev->lch=erase_aux(prev->lch->val,prev->lch,_found);
162 --prev->lSize;
163 }
164 else
165 {
166 _cur->val=_cur->rch->val;
167 _cur->rch=erase_aux(_cur->rch->val,_cur->rch,_found);
168 --_cur->rSize;
169 }
170 return _cur;
171 }
172 }
173
174 Sbt& operator >> (const T& _val)
175 {
176 bool found=false;
177 root=erase_aux(_val,root,found);
178 return *this;
179 }
180
181 int notMoreCount(const T& _val)
182 {
183 Node* cur=root;
184 int res=0;
185 while(cur)
186 {
187 if(cmp(_val,cur->val)) cur=cur->lch;
188 else
189 {
190 res+=(cur->lSize+1);
191 cur=cur->rch;
192 }
193 }
194 return res;
195 }
196
197 int lessCount(const T& _val)
198 {
199 Node* cur=root;
200 int res=0;
201 while(cur)
202 {
203 if(cmp(cur->val,_val))
204 {
205 res+=(cur->lSize+1);
206 cur=cur->rch;
207 }
208 else cur=cur->lch;
209 }
210 return res;
211 }
212 };
213
214 const int bktSize=512;
215 const int bktMaxIdx=bktSize-1;
216 const int bktCount=128;
217 const int bktDigit=9;
218
219 #include <functional>
220 #include <algorithm>
221
222 int unOrd[bktCount*bktSize];
223
224 using std::less;
225 SizeBlcTree<int,less<int> > all;
226 SizeBlcTree<int,less<int> > bucket[bktCount];
227 int N,K;
228 int cs;
229
230 #include <cstdio>
231
232 void init()
233 {
234 scanf("%d%d",&N,&K);
235 for(int i=0;i<N;i++)
236 {
237 scanf("%d",unOrd+i);
238 all<<unOrd[i];
239 bucket[i>>bktDigit] << unOrd[i];
240 }
241 }
242
243 inline void enumerate(int _rL,int _rR,int _val,int& _less,int& _notMore)
244 {
245 for(int i=_rL;i<=_rR;i++) if(unOrd[i]<=_val)
246 {
247 _notMore++;
248 if(unOrd[i]<_val) _less++;
249 }
250 }
251
252 int getAns(int _rL,int _rR,int _k)
253 {
254 int bktL = _rL>>bktDigit;
255 int bktR = _rR>>bktDigit;
256
257 int prevVal;
258 SbtNode<int> *cur=all.root;
259 while(cur)
260 {
261 int notMore=0;
262 int less=0;
263 if(bktL==bktR) enumerate(_rL,_rR,cur->val,less,notMore);
264 else
265 {
266 for(int i=bktL+1;i<bktR;i++)
267 {
268 notMore += bucket[i].notMoreCount(cur->val);
269 less += bucket[i].lessCount(cur->val);
270 }
271 enumerate(_rL,((bktL+1)<<bktDigit)-1,cur->val,less,notMore);
272 enumerate(bktR<<bktDigit,_rR,cur->val,less,notMore);
273 }
274 if(less<_k && notMore>=_k) return cur->val;
275 prevVal=cur->val;
276 if(less>=_k) cur=cur->lch;
277 else cur=cur->rch;
278 }
279 return prevVal;
280 }
281
282 void solve()
283 {
284 char cmd;
285 do cmd=getchar(); while(cmd==' ' || cmd=='\n');
286 if(cmd=='Q')
287 {
288 int rL,rR,k;
289 scanf("%d%d%d",&rL,&rR,&k);
290 printf("%d\n",getAns(rL-1,rR-1,k));
291 }
292 else
293 {
294 int pos,v;
295 scanf("%d%d",&pos,&v);
296 --pos;
297 all<<v;
298 bucket[pos>>bktDigit] >> unOrd[pos];
299 bucket[pos>>bktDigit] << (unOrd[pos]=v) ;
300 }
301 }
302
303 void reset()
304 {
305 all.clear();
306 int used=N>>bktDigit;
307 for(int i=0;i<=used;i++) bucket[i].clear();
308 }
309
310 int main()
311 {
312 scanf("%d",&cs);
313 while(cs--)
314 {
315 init();
316 while(K--) solve();
317 reset();
318 }
319 return 0;
320 }
View Code
簡析：
可以和我的這篇隨筆進行對比：http://www.cnblogs.com/Onlynagesha/p/5353531.html
前面將近2/3都是SBT的模板
平方分割的大致思路和靜態第k大是一樣的，中間分塊高效維護，然後枚舉兩邊的零頭
但在動態第k大問題中，每個桶維護的都是一棵平衡樹。這樣我們便可以高效的修改。
若要進行高效的二分，我們還要維護一顆“總的”平衡樹all，存放當前所有的數值。
二分的時候從all的根節點開始，邊界是走到葉子節點。二分的每一步都有三種可能：
（1）當前節點就是答案
（2）當前節點的值過大，那麼取下一個值為其左孩子
（3）當前節點的值過大，那麼取下一個值為其右孩子
注意體會基於樹的二分和基於區間的二分的差異。前者難以保證“可能”會成為答案的值被保留（因為每走一步當前的值就被“丟棄”了），而後者可以
另外維護all的時候還有一個小技巧：修改數值時只需將新值插入而不需將舊值刪去，這樣可以省下一點時間常數
被“刪去”的值在之後的二分過程中一定不會滿足第（1）種可能
