-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcartesiantree.sublime-snippet
62 lines (57 loc) · 1.14 KB
/
cartesiantree.sublime-snippet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
<snippet>
<content><![CDATA[
struct Node{
int val, prior, sz$1;
Node *l, *r;
};
Node* init(int _val$2) {
Node *ans = new Node();
ans -> val = _val;
ans -> prior = rand();
ans -> sz = 1;$3
return ans;
}
int get_sz(Node *a) {
if (!a)
return 0;
return a -> sz;
}
void upd(Node *a) {
a -> sz = get_sz(a -> l) + get_sz(a -> r) + 1;$4
}
Node *merge(Node *a, Node *b) {
if (!a)
return b;
if (!b)
return a;
if (a -> prior > b -> prior) {
a -> r = merge(a -> r, b);
upd(a);
return a;
} else {
b -> l = merge(a, b -> l);
upd(b);
return b;
}
}
pair <Node*, Node*> split(Node *a, int k) {
if (!a)
return {0, 0};
if (get_sz(a -> l) < k) {
auto b = split(a -> r, k - get_sz(a -> l) - 1);
a -> r = b.fs;
upd(a);
return {a, b.sc};
} else {
auto b = split(a -> l, k);
a -> l = b.sc;
upd(a);
return {b.fs, a};
}
}
]]></content>
<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
<tabTrigger>cartesiantree</tabTrigger>
<!-- Optional: Set a scope to limit where the snippet will trigger -->
<!-- <scope>source.python</scope> -->
</snippet>