Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class cart_tree {
- typedef struct _Node {
- int x, y;
- ll sum;
- int cnt;
- _Node *l, *r;
- _Node(int _x) : x(_x), y(rand()), sum(_x), cnt(1), l(0), r(0) {}
- ~_Node() {
- if (l) delete l;
- if (r) delete r;
- }
- void recalc() {
- sum = x; cnt = 1;
- if (l) sum += l->sum, cnt += l->cnt;
- if (r) sum += r->sum, cnt += r->cnt;
- }
- } *Node;
- Node merge(Node l, Node r) {
- if (!l) return r;
- if (!r) return l;
- if (l->y < r->y) {
- l->r = merge(l->r, r);
- return l->recalc(), l;
- } else {
- r->l = merge(l, r->l);
- return r->recalc(), r;
- }
- }
- void split(Node v, int key, Node &l, Node &r) {
- l = r = 0;
- if (!v) return;
- Node tmp;
- if (v->x <= key) {
- split(v->r, key, tmp, r);
- v->r = tmp;
- l = v;
- } else {
- split(v->l, key, l, tmp);
- v->l = tmp;
- r = v;
- }
- v->recalc();
- }
- void print(Node v) {
- if (!v) { eoprintf("null\n"); return; }
- eoprintf("x=%d, sum=%lld, cnt=%d\n", v->x, v->sum, v->cnt);
- eoff += 2;
- print(v->l);
- print(v->r);
- eoff -= 2;
- }
- Node root;
- public:
- cart_tree() : root(0){}
- void insert(int x) {
- Node l, r;
- split(root, x, l, r);
- root = merge(merge(l, new _Node(x)), r);
- }
- pair<ll, int> getLeqThan(int x) {
- Node l, r;
- split(root, x, l, r);
- pair<ll, int> res(0, 0);
- if (l) res = mp(l->sum, l->cnt);
- root = merge(l, r);
- return res;
- }
- };
Add Comment
Please, Sign In to add comment