summaryrefslogtreecommitdiff
path: root/datastructures/treap2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures/treap2.cpp')
-rw-r--r--datastructures/treap2.cpp30
1 files changed, 15 insertions, 15 deletions
diff --git a/datastructures/treap2.cpp b/datastructures/treap2.cpp
index 10168ca..e40da0d 100644
--- a/datastructures/treap2.cpp
+++ b/datastructures/treap2.cpp
@@ -3,7 +3,7 @@ struct Treap {
struct Node {
ll val;
int prio, size = 1, l = -1, r = -1;
- Node (ll x) : val(x), prio(rng()) {}
+ Node(ll x): val(x), prio(rng()) {}
};
vector<Node> treap;
@@ -15,35 +15,35 @@ struct Treap {
void upd(int v) {
if (v < 0) return;
- auto *V = &treap[v];
- V->size = 1 + getSize(V->l) + getSize(V->r);
+ auto &V = treap[v];
+ V.size = 1 + getSize(V.l) + getSize(V.r);
// Update Node Code
}
void push(int v) {
if (v < 0) return;
- //auto *V = &treap[v];
- //if (V->lazy) {
+ //auto &V = treap[v];
+ //if (V.lazy) {
// Lazy Propagation Code
- // if (V->l >= 0) treap[V->l].lazy = true;
- // if (V->r >= 0) treap[V->r].lazy = true;
- // V->lazy = false;
+ // if (V.l >= 0) treap[V.l].lazy = true;
+ // if (V.r >= 0) treap[V.r].lazy = true;
+ // V.lazy = false;
//}
}
pair<int, int> split(int v, int k) {
if (v < 0) return {-1, -1};
- auto *V = &treap[v];
+ auto &V = treap[v];
push(v);
- if (getSize(V->l) >= k) { // "V->val >= k" for lower_bound(k)
- auto [left, right] = split(V->l, k);
- V->l = right;
+ if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
+ auto [left, right] = split(V.l, k);
+ V.l = right;
upd(v);
return {left, v};
} else {
// and only "k"
- auto [left, right] = split(V->r, k - getSize(V->l) - 1);
- V->r = left;
+ auto [left, right] = split(V.r, k - getSize(V.l) - 1);
+ V.r = left;
upd(v);
return {v, right};
}}
@@ -66,7 +66,7 @@ struct Treap {
void insert(int i, ll val) { // and i = val
auto [left, right] = split(root, i);
treap.emplace_back(val);
- left = merge(left, sz(treap) - 1);
+ left = merge(left, ssize(treap) - 1);
root = merge(left, right);
}