diff options
| -rw-r--r-- | TestMakefile | 5 | ||||
| -rw-r--r-- | datastructures/treap2.cpp | 30 |
2 files changed, 18 insertions, 17 deletions
diff --git a/TestMakefile b/TestMakefile index 59a902f..58d2678 100644 --- a/TestMakefile +++ b/TestMakefile @@ -13,10 +13,11 @@ TESTS := \ datastructures/test/waveletTree \ datastructures/test/fenwickTree \ datastructures/test/fenwickTree2 \ - datastructures/test/monotonicConvexHull \ - datastructures/test/persistent \ + datastructures/test/treap2 \ datastructures/test/sparseTable \ datastructures/test/sparseTableDisjoint \ + datastructures/test/monotonicConvexHull \ + datastructures/test/persistent \ graph/test/binary_lifting \ graph/test/LCA_sparse \ math/test/binomial0 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); } |