hdu 4006/AvlTree，
原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4006
這道題以前用c語言寫的Avltree水過了。。
現在接觸了c++重寫一遍。。。
由於沒有刪除操作故不帶垃圾回收，具體如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #define Max_N 1000100
5 inline int max(int &a, int &b){
6 return a > b ? a : b;
7 }
8 struct Node *null;
9 struct Node{
10 int v, s, Height;
11 Node *ch[2];
12 inline void
13 set(int H = 0, int _v = 0, int _s = 0, Node *p = NULL){
14 v = _v, s = _s, Height = H;
15 ch[0] = ch[1] = p;
16 }
17 inline void push_up(){
18 s = ch[0]->s + ch[1]->s + 1;
19 int t1 = ch[0] == null ? -1 : ch[0]->Height;
20 int t2 = ch[1] == null ? -1 : ch[1]->Height;
21 Height = max(t1, t2) + 1;
22 }
23 };
24 struct AvlTree{
25 Node *tail, *root;
26 Node stack[Max_N];
27 int top;
28 void init(){
29 tail = &stack[0];
30 null = tail++;
31 null->set();
32 root = null;
33 }
34 Node *newNode(int v){
35 Node *p = tail++;
36 p->set(0, v, 1, null);
37 return p;
38 }
39 inline void rotate(Node* &x, int d){
40 Node *k = x->ch[!d];
41 x->ch[!d] = k->ch[d];
42 k->ch[d] = x;
43 k->s = x->s;
44 x->push_up();
45 x = k;
46 }
47 void Maintain(Node* &x, int d){
48 if (x->ch[d]->Height - x->ch[!d]->Height == 2){
49 if (x->ch[d]->ch[d]->Height - x->ch[d]->ch[!d]->Height == 1){
50 rotate(x, !d);
51 } else if (x->ch[d]->ch[d]->Height - x->ch[d]->ch[!d]->Height == -1){
52 rotate(x->ch[d], d), rotate(x, !d);
53 }
54 }
55 }
56 void insert(Node* &x, int v){
57 if (x == null){
58 x = newNode(v);
59 return;
60 } else {
61 int d = v > x->v;
62 insert(x->ch[d], v);
63 x->push_up();
64 Maintain(x, d);
65 }
66 }
67 int find_kth(Node *x, int k){
68 int t = 0;
69 for (; x != null;){
70 t = x->ch[0]->s;
71 if (k == t + 1) break;
72 else if (k <= t) x = x->ch[0];
73 else k -= t + 1, x = x->ch[1];
74 }
75 return x->v;
76 }
77 }Avl;
78 int main(){
79 #ifdef LOCAL
80 freopen("in.txt", "r", stdin);
81 freopen("out.txt", "w+", stdout);
82 #endif
83 char ch;
84 int i, n, k, d;
85 while (~scanf("%d %d", &n, &k)){
86 Avl.init();
87 for (i = 0; i < n; i++){
88 getchar();
89 scanf("%c", &ch);
90 if ('I' == ch)
91 scanf("%d", &d), Avl.insert(Avl.root, d);
92 else
93 printf("%d\n", Avl.find_kth(Avl.root, Avl.root->s - k + 1));
94 }
95 }
96 return 0;
97 }
View Code
