首页 > 代码库 > SGU 263. Towers
SGU 263. Towers
各种操作：
- put x c:表示在第 x 列上增加 c 个积木(c>0)。
- tput t x c:表示在塔 t 的第 x 列上增加 c 个积木(c>0)。
- towers:询问共有几座塔。
- cubes t:询问第 t 座塔共有几个积木。
- length t:询问第 t 座塔的长度。
- tcubes t x:询问第 t 座塔的第 x 列有几个积木。
对应做法：
- towers: 由于要查询tower的数目，以及删除一个tower，加入一个tower，考虑使用平衡树维护。
- put: 首先加积木这一件事情只会使得tower发生合并操作对吧，所以可以用并查集维护点属于那个tower。关于合并积木：先查找这个位置是否本来就有积木，如果有，加上就行拉，更新一下BST中的端点的cubes就行拉；否则加上之后插入BST内，如果其左边有towers，或者右边有towers，或者两边都有删除靠右边的节点，将信息传递到左边的节点，然后在并查集内把父亲指向左边节点的左端点，没拉。
- tput: 在某个tower内加积木，如果我知道某个tower的左端点，直接加就行了，之后更新BST内节点即可。
- cubes: 直接把大小放到tower的最左边的端点中，查询直接输出即可。
- lengths: 同上。
- tcubes: 同tput。
由于要求支持k大操作，set不适用，只好手写平衡树拉>_<!!。
notice:
- 删除节点旋转时要记录方向 int d = t->ch[0]->fix < t->ch[1]->fix; ，千万不要在这里图方便 else rot(t, t->ch[0]->fix < t->ch[1]->fix), del(t->ch[t->ch[0]->fix < t->ch[1]->fix], pos); ，因为已经把儿子转走了，如上定RE。
- 新建指针节点一定将其指向NULL，无论之后会不会给它赋值。
- 手残打错变量名。。。为什么每次敲数据结构题都会敲错变量名。。。
CODE:
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 // notice119 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 // notice135 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_JUDGE179 srand((int)time(NULL));180 #endif181 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。