各种操作：
- 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[]->fix < t->ch[]->fix; ，千万不要在这里图方便 else rot(t, t->ch[]->fix < t->ch[]->fix), del(t->ch[t->ch[]->fix < t->ch[]->fix], pos); ，因为已经把儿子转走了，如上定RE。
- 新建指针节点一定将其指向NULL，无论之后会不会给它赋值。
- 手残打错变量名。。。为什么每次敲数据结构题都会敲错变量名。。。
CODE:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + ;
const int maxp = 1e6; int n;
int fa[maxn], num[maxn]; int test_on; int find_fa(int x) {
if(fa[x] != x) fa[x] = find_fa(fa[x]);
return fa[x];
} class BST {
private:
struct treap_node {
treap_node *ch[];
int fix, size, pos, cubes, length;
treap_node() {
ch[] = ch[] = NULL;
}
treap_node(int _pos, int _cubes, int _lengh) {
pos = _pos, cubes = _cubes, length = _lengh;
ch[] = ch[] = NULL;
size = ;
fix = rand();
}
} *T;
void maintain(treap_node *x) {
if(x) {
x->size = ;
if(x->ch[]) x->size += x->ch[]->size;
if(x->ch[]) x->size += x->ch[]->size;
}
}
void rot(treap_node *&x, int d) {
treap_node *y = x->ch[d ^ ];
x->ch[d ^ ] = y->ch[d];
y->ch[d] = x;
maintain(x), maintain(y);
x = y;
}
void insert(treap_node *&t, int p, int c, int l) {
if(t == NULL) {
t = new treap_node(p, c, l);
} else {
if(p < t->pos) {
insert(t->ch[], p, c, l);
if(t->ch[]->fix < t->fix) rot(t, );
} else {
insert(t->ch[], p, c, l);
if(t->ch[]->fix < t->fix) rot(t, );
}
}
maintain(t);
}
void del(treap_node *&t, int pos) {
if(t->pos == pos) {
if(!(t->ch[]) || !(t->ch[])) {
treap_node *p = t;
if(t->ch[]) p = t->ch[];
else p = t->ch[];
t = NULL;
delete t;
t = p;
} else {
int d = t->ch[]->fix < t->ch[]->fix;
// notice
rot(t, d);
del(t->ch[d], pos);
}
} else del(t->ch[t->pos < pos], pos);
if(t) maintain(t);
}
treap_node *select(int k) {
treap_node *t = T;
int size;
while() {
size = t->ch[] ? t->ch[]->size : ;
if(k <= size) {
t = t->ch[];
} else if(k > size + ) {
k -= size + ;
t = t->ch[];
} else break;
}
return t;
}
treap_node *find(treap_node *t, int pos) {
if(t == NULL || t->pos == pos) return t;
return find(t->ch[t->pos < pos], pos);
} public: void print(treap_node *node) {
if(node == NULL) return ;
print(node->ch[]);
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);
printf(" ch[0] :%d ch[1] :%d\n", node->ch[], node->ch[]);
print(node->ch[]);
} int f, t, x, c;
treap_node *r;
void put() {
scanf("%d%d", &x, &c);
f = find_fa(x);
num[x] += c;
r = find(T, f);
if(r == NULL) {
insert(T, x, num[x], );
treap_node *p, *q;
p = q = NULL;
// notice
r = find(T, f);
if( < x - ) p = find(T, find_fa(x - ));
if(x + <= maxp) q = find(T, find_fa(x + ));
if(p != NULL || q != NULL) {
if(p != NULL) {
fa[r->pos] = p->pos;
p->cubes += r->cubes;
p->length += r->length;
del(T, r->pos);
r = p;
}
if(q != NULL) {
fa[q->pos] = r->pos;
r->cubes += q->cubes;
r->length += q->length;
// notice
del(T, q->pos);
}
}
} else {
r->cubes += c;
}
/*
r = select(1);
printf(" %d\n", r->length);
printf("%d\n", test_on);
print(T);
puts("");
*/
}
void tcubes() {
scanf("%d%d", &t, &x);
r = select(t);
printf("%d cubes in %dth column of %dth tower\n", num[r->pos + x - ], x, t);
}
void tput() {
scanf("%d%d%d", &t, &x, &c);
r = select(t);
num[r->pos + x - ] += c;
r->cubes += c;
}
void length() {
scanf("%d", &t);
r = select(t);
printf("length of %dth tower is %d\n", t, r->length);
}
void towers() {
printf("%d towers\n", T ? T->size : );
}
void cubes() {
scanf("%d", &t);
r = select(t);
printf("%d cubes in %dth tower\n", r->cubes, t);
}
} T; char ope[];
int main() {
#ifdef ONLINE_JUDGE
srand((int)time(NULL));
#endif for(int i = ; i < maxn; ++i) fa[i] = i;
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
// test_on = i;
// printf("%d ", test_on);
scanf("%s", ope);
if(ope[] == 'p') {
T.put();
} else if(ope[] == 't' && ope[] == 'o') {
T.towers();
} else if(ope[] == 't' && ope[] == 'p') {
// puts("");
T.tput();
} else if(ope[] == 'c') {
T.cubes();
} else if(ope[] == 'l') {
T.length();
} else if(ope[] == 't' && ope[] == 'c') {
T.tcubes();
}
} return ;
}