poj 1442 Black Box

http://poj.org/problem?id=1442

　　简单BST求k大数，在线插入各个元素并查询。

SBT版：

View Code 
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 
  8 using namespace std;
  9 typedef vector<int> vi;
 10 
 11 struct SBTNode{
 12     SBTNode *left, *right;
 13     int key, size;
 14     SBTNode(int k){
 15         key = k;
 16         size = 1;
 17         left = right = NULL;
 18     }
 19 };
 20 
 21 struct SBT{
 22     SBTNode *root;
 23 
 24     SBT(){
 25         root = NULL;
 26     }
 27 
 28     void rightRotate(SBTNode *&x){
 29         SBTNode *y = x->left;
 30 
 31         x->left = y->right;
 32         y->right = x;
 33         y->size = x->size;
 34 
 35         int ls = x->left ? x->left->size : 0;
 36         int rs = x->right ? x->right->size : 0;
 37 
 38         x->size = ls + rs + 1;
 39         x = y;
 40     }
 41 
 42     void leftRotate(SBTNode *&x){
 43         SBTNode *y = x->right;
 44 
 45         x->right = y->left;
 46         y->left = x;
 47         y->size = x->size;
 48 
 49         int ls = x->left ? x->left->size : 0;
 50         int rs = x->right ? x->right->size : 0;
 51 
 52         x->size = ls + rs + 1;
 53         x = y;
 54     }
 55 
 56     void maintain(SBTNode *&T, bool rightDeeper){
 57         if (!T) return ;
 58         if (!rightDeeper){
 59             if (T->left == NULL) return ;
 60 
 61             int rs = T->right ? T->right->size : 0;
 62 
 63             if (T->left->left && T->left->left->size > rs){
 64                 rightRotate(T);
 65             }
 66             else if (T->left->right && T->left->right->size > rs){
 67                 leftRotate(T->left);
 68                 rightRotate(T);
 69             }
 70             else return ;
 71         }
 72         else {
 73             if (T->right == NULL) return ;
 74 
 75             int ls = T->left ? T->left->size : 0;
 76 
 77             if (T->right->right && T->right->right->size > ls){
 78                 leftRotate(T);
 79             }
 80             else if (T->right->left && T->right->left->size > ls){
 81                 rightRotate(T->right);
 82                 leftRotate(T);
 83             }
 84             else return ;
 85         }
 86         maintain(T->left, false);
 87         maintain(T->right, true);
 88         maintain(T, false);
 89         maintain(T, true);
 90     }
 91 
 92     void ins(SBTNode *&T, SBTNode *x){
 93         if (!T){
 94             T = x;
 95             return ;
 96         }
 97         T->size++;
 98         if (x->key < T->key){
 99             ins(T->left, x);
100         }
101         else{
102             ins(T->right, x);
103         }
104         maintain(T, x->key >= T->key);
105     }
106 
107     void del(SBTNode *&T, int key){
108         if (!T) return ;
109         T->size--;
110         if (key < T->key) del(T->left, key);
111         else if (key > T->key) del(T->right, key);
112         else{
113             SBTNode *t;
114 
115             if (!T->left && !T->right){
116                 delete T;
117                 T = NULL;
118             }
119             else if (!T->right){
120                 t = T;
121                 T = T->left;
122                 delete t;
123             }
124             else if (!T->left){
125                 t = T;
126                 T = T->right;
127                 delete t;
128             }
129             else{
130                 t = T->right;
131                 while (t->left) t = t->left;
132                 T->key = t->key;
133                 del(T->right, t->key);
134             }
135         }
136     }
137 
138     int find(SBTNode *T, int k){ // find the kth min
139         SBTNode *p = T;
140 
141         if (k <= 0) return 0;
142         if (k > p->size) return -1;
143 
144         while (true){
145             int ls = p->left ? p->left->size : 0;
146 
147 //printf("k %d  p %d\n", k, p);
148             if (k == ls + 1) return p->key;
149             if (k <= ls) p = p->left;
150             else k -= ls + 1, p = p->right;
151         }
152     }
153 
154     void print(SBTNode *T){
155         if (!T) return ;
156         printf("cur %d : key %d left %d right %d size %d\n", T, T->key, T->left, T->right, T->size);
157         print(T->left);
158         print(T->right);
159     }
160 
161     void delAll(SBTNode *T){
162         if (T->left) delAll(T->left);
163         if (T->right) delAll(T->right);
164         delete T;
165     }
166 }T;
167 
168 queue<int> op, blackBox;
169 
170 void deal(){
171     T.root = NULL;
172     SBTNode *tmp;
173 
174     int cur = 1, cnt = 0;
175 
176     while (blackBox.size() && op.size()){
177         int a = blackBox.front();
178 
179         tmp = new SBTNode(a);
180         blackBox.pop();
181         T.ins(T.root, tmp);
182         cnt++;
183         while (op.size() && op.front() == cnt){
184 //T.print(T.root);
185             printf("%d\n", T.find(T.root, cur));
186             cur++;
187             op.pop();
188         }
189     }
190     T.delAll(T.root);
191 }
192 
193 int main(){
194     int n, m;
195 
196     while (~scanf("%d%d", &n, &m)){
197         while (blackBox.size()) blackBox.pop();
198         while (op.size()) op.pop();
199 
200         while (n--){
201             int a;
202 
203             scanf("%d", &a);
204             blackBox.push(a);
205         }
206         while (m--){
207             int a;
208 
209             scanf("%d", &a);
210             op.push(a);
211         }
212         deal();
213     }
214 
215     return 0;
216 }

Treap版：

View Code 
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cassert>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <queue>
  8 #include <ctime>
  9 
 10 using namespace std;
 11 
 12 struct Node{
 13     Node *child[2];
 14     int key;
 15     int fix;
 16     int size;
 17     Node(int k){
 18         key = k;
 19         fix = rand();
 20         size = 1;
 21         child[0] = child[1] = NULL;
 22     }
 23 };
 24 
 25 struct Treap{
 26     Node *root;
 27     int size;
 28     Treap(){
 29         srand(time(NULL));
 30         root = NULL;
 31         size = 0;
 32     }
 33 };
 34 
 35 void rotateTreap(Node *&rt, bool left){
 36     bool right = !left;
 37     Node *p = rt->child[right];
 38 
 39     rt->child[right] = p->child[left];
 40     p->child[left] = rt;
 41     p->size = rt->size;
 42 
 43     int ls = rt->child[left] ? rt->child[left]->size : 0;
 44     int rs = rt->child[right] ? rt->child[right]->size : 0;
 45 
 46     rt->size = ls + rs + 1;
 47     rt = p;
 48 }
 49 
 50 void insertTreap(Node *&rt, Node *x){
 51     if (!rt){
 52         rt = x;
 53 
 54         return ;
 55     }
 56 
 57     rt->size++;
 58     if (x->key < rt->key){
 59         insertTreap(rt->child[true], x);
 60         if (rt->child[true]->fix > rt->fix){
 61             rotateTreap(rt, false);
 62         }
 63     }
 64     else{
 65         insertTreap(rt->child[false], x);
 66         if (rt->child[false]->fix > rt->fix){
 67             rotateTreap(rt, true);
 68         }
 69     }
 70 }
 71 
 72 void deleteAllTreap(Node *rt){
 73     if (!rt) return ;
 74     deleteAllTreap(rt->child[true]);
 75     deleteAllTreap(rt->child[false]);
 76     delete rt;
 77 }
 78 
 79 int findTreap(Node *rt, int pos){
 80     if (!rt || rt->size < pos) return -1;
 81 
 82     Node *p = rt;
 83 
 84     while (true){
 85 //printf("pos %d\n", pos);
 86         int ln = p->child[true] ? p->child[true]->size : 0;
 87 
 88         if (ln + 1 == pos) return p->key;
 89         else if (ln >= pos) p = p->child[true];
 90         else pos -= ln + 1, p = p->child[false];
 91     }
 92 }
 93 
 94 void print(Node *rt){
 95     if (!rt) return ;
 96     printf("%d key %d fix %d left %d right %d size %d\n", rt, rt->key, rt->fix, rt->child[true], rt->child[false], rt->size);
 97     print(rt->child[true]);
 98     print(rt->child[false]);
 99 }
100 
101 queue<int> blackBox, op;
102 
103 void deal(){
104     Treap T = Treap();
105 
106     int cur = 1;
107 
108     while (blackBox.size() && op.size()){
109         int t = blackBox.front();
110         blackBox.pop();
111 
112         Node *tmp = new Node(t);
113 
114         insertTreap(T.root, tmp);
115 //print(T.root);
116 //printf("insert %d\n", tmp);
117         T.size++;
118 
119         while (op.size() && T.size == op.front()){
120             printf("%d\n", findTreap(T.root, cur));
121             op.pop();
122             cur++;
123         }
124     }
125     deleteAllTreap(T.root);
126 }
127 
128 int main(){
129     int n, m;
130 
131     while (~scanf("%d%d", &n, &m)){
132         int a;
133 
134         while (blackBox.size()) blackBox.pop();
135         while (op.size()) op.pop();
136 
137         while (n--){
138             scanf("%d", &a);
139             blackBox.push(a);
140         }
141         while (m--){
142             scanf("%d", &a);
143             op.push(a);
144         }
145         deal();
146     }
147 
148     return 0;
149 }

 　　这题还可以用线段树或者树状数组离线离散化处理！ 

——written by Lyon

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/LyonLys/p/poj_1442_Lyon.html