| 7 | void augment(node *t) { |
| 8 | t->sz = 1 + tsize(t->l) + tsize(t->r); } |
| 9 | pair<node*,node*> split(node *t, int x) { |
| 10 | if (!t) return make_pair((node*)NULL,(node*)NULL); |
| 11 | if (t->x < x) { |
| 12 | pair<node*,node*> res = split(t->r, x); |
| 13 | t->r = res.first; augment(t); |
| 14 | return make_pair(t, res.second); } |
| 15 | pair<node*,node*> res = split(t->l, x); |
| 16 | t->l = res.second; augment(t); |
| 17 | return make_pair(res.first, t); } |
| 18 | node* merge(node *l, node *r) { |
| 19 | if (!l) return r; if (!r) return l; |
| 20 | if (l->y > r->y) { |