SGU 263. Towers

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 1e6 + 10;
  4 const int maxp = 1e6;
  5 
  6 int n;
  7 int fa[maxn], num[maxn];
  8 
  9 int test_on;
 10 
 11 int find_fa(int x) {
 12     if(fa[x] != x) fa[x] = find_fa(fa[x]);
 13     return fa[x];
 14 }
 15 
 16 
 17 class BST {
 18 private:
 19     struct treap_node {
 20         treap_node *ch[2];
 21         int fix, size, pos, cubes, length;
 22         treap_node() {
 23             ch[0] = ch[1] = NULL;
 24         }
 25         treap_node(int _pos, int _cubes, int _lengh) {
 26             pos = _pos, cubes = _cubes, length = _lengh;
 27             ch[0] = ch[1] = NULL;
 28             size = 1;
 29             fix = rand();
 30         }
 31     } *T;
 32     void maintain(treap_node *x) {
 33         if(x) {
 34             x->size = 1;
 35             if(x->ch[0]) x->size += x->ch[0]->size;
 36             if(x->ch[1]) x->size += x->ch[1]->size;
 37         }
 38     }
 39     void rot(treap_node *&x, int d) {
 40         treap_node *y = x->ch[d ^ 1];
 41         x->ch[d ^ 1] = y->ch[d];
 42         y->ch[d] = x;
 43         maintain(x), maintain(y);
 44         x = y;
 45     }
 46     void insert(treap_node *&t, int p, int c, int l) {
 47         if(t == NULL) {
 48             t = new treap_node(p, c, l);
 49         } else {
 50             if(p < t->pos) {
 51                 insert(t->ch[0], p, c, l);
 52                 if(t->ch[0]->fix < t->fix) rot(t, 1);
 53             } else {
 54                 insert(t->ch[1], p, c, l);
 55                 if(t->ch[1]->fix < t->fix) rot(t, 0);
 56             }
 57         }
 58         maintain(t);
 59     }
 60     void del(treap_node *&t, int pos) {
 61         if(t->pos == pos) {
 62             if(!(t->ch[0]) || !(t->ch[1])) {
 63                 treap_node *p = t;
 64                 if(t->ch[0]) p = t->ch[0];
 65                 else p = t->ch[1];
 66                 t = NULL;
 67                 delete t;
 68                 t = p;
 69             } else {
 70                 int d = t->ch[0]->fix < t->ch[1]->fix;
 71                 // notice
 72                 rot(t, d);
 73                 del(t->ch[d], pos);
 74             }
 75         } else del(t->ch[t->pos < pos], pos);
 76         if(t) maintain(t);
 77     }
 78     treap_node *select(int k) {
 79         treap_node *t = T;
 80         int size;
 81         while(1) {
 82             size = t->ch[0] ? t->ch[0]->size : 0;
 83             if(k <= size) {
 84                 t = t->ch[0];
 85             } else if(k > size + 1) {
 86                 k -= size + 1;
 87                 t = t->ch[1];
 88             } else break;
 89         }
 90         return t;
 91     }
 92     treap_node *find(treap_node *t, int pos) {
 93         if(t == NULL || t->pos == pos) return t;
 94         return find(t->ch[t->pos < pos], pos);
 95     }
 96 
 97 public:
 98 
 99     void print(treap_node *node) {
100         if(node == NULL) return ;
101         print(node->ch[0]);
102         printf("address :%d  size :%d  fix :%d\n    pos :%d  cubes :%d  length :%d\n", node, node->size, node->fix, node->pos, node->cubes, node->length);
103         printf("    ch[0] :%d ch[1] :%d\n", node->ch[0], node->ch[1]);
104         print(node->ch[1]);
105     }
106 
107     int f, t, x, c;
108     treap_node *r;
109     void put() {
110         scanf("%d%d", &x, &c);
111         f = find_fa(x);
112         num[x] += c;
113         r = find(T, f);
114         if(r == NULL) {
115             insert(T, x, num[x], 1);
116             treap_node *p, *q;
117             p = q = NULL;
118             // notice
119             r = find(T, f);
120             if(0 < x - 1) p = find(T, find_fa(x - 1));
121             if(x + 1 <= maxp) q = find(T, find_fa(x + 1));
122             if(p != NULL || q != NULL) {
123                 if(p != NULL) {
124                     fa[r->pos] = p->pos;
125                     p->cubes += r->cubes;
126                     p->length += r->length;
127                     del(T, r->pos);
128                     r = p;
129                 }
130                 if(q != NULL) {
131                     fa[q->pos] = r->pos;
132                     r->cubes += q->cubes;
133                     r->length += q->length;
134                     // notice
135                     del(T, q->pos);
136                 }
137             }
138         } else {
139             r->cubes += c;
140         }
141         /*
142         r = select(1);
143         printf(" %d\n", r->length);
144         printf("%d\n", test_on);
145         print(T);
146         puts("");
147         */
148     }
149     void tcubes() {
150         scanf("%d%d", &t, &x);
151         r = select(t);
152         printf("%d cubes in %dth column of %dth tower\n", num[r->pos + x - 1], x, t);
153     }
154     void tput() {
155         scanf("%d%d%d", &t, &x, &c);
156         r = select(t);
157         num[r->pos + x - 1] += c;
158         r->cubes += c;
159     }
160     void length() {
161         scanf("%d", &t);
162         r = select(t);
163         printf("length of %dth tower is %d\n", t, r->length);
164     }
165     void towers() {
166         printf("%d towers\n", T ? T->size : 0);
167     }
168     void cubes() {
169         scanf("%d", &t);
170         r = select(t);
171         printf("%d cubes in %dth tower\n", r->cubes, t);
172     }
173 } T;
174 
175 
176 char ope[10];
177 int main() {
178 #ifdef ONLINE_JUDGE
179     srand((int)time(NULL));
180 #endif
181 
182     for(int i = 0; i < maxn; ++i) fa[i] = i;
183     scanf("%d", &n);
184     for(int i = 1; i <= n; ++i) {
185 //        test_on = i;
186 //        printf("%d ", test_on);
187         scanf("%s", ope);
188         if(ope[0] == ‘p‘) {
189             T.put();
190         } else if(ope[0] == ‘t‘ && ope[1] == ‘o‘) {
191             T.towers();
192         } else if(ope[0] == ‘t‘ && ope[1] == ‘p‘) {
193 //            puts("");
194             T.tput();
195         } else if(ope[0] == ‘c‘) {
196             T.cubes();
197         } else if(ope[0] == ‘l‘) {
198             T.length();
199         } else if(ope[0] == ‘t‘ && ope[1] == ‘c‘) {
200             T.tcubes();
201         }
202     }
203 
204     return 0;
205 }