diff options
Diffstat (limited to 'content/datastructures/lazyPropagation.cpp')
| -rw-r--r-- | content/datastructures/lazyPropagation.cpp | 37 |
1 files changed, 19 insertions, 18 deletions
diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp index ab91364..a5be822 100644 --- a/content/datastructures/lazyPropagation.cpp +++ b/content/datastructures/lazyPropagation.cpp @@ -1,23 +1,22 @@ struct SegTree { using T = ll; using U = ll; - int n; static constexpr T E = 0; // Neutral element for combine - static constexpr U UF = INF; // Unused value by updates - vector<T> tree; + static constexpr U UF = 1e18; // Unused value by updates + int n; + vector<T> tree; vector<U> lazy; int h; - vector<U> lazy; - vector<int> k; // size of segments (optional) + vector<ll> k; // size of segments (optional) - SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E), + SegTree(const vector<T>& a) : n(ssize(a) + 1), tree(2 * n, E), //SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def), - h(__lg(2 * n)), lazy(n, UF), k(2 * n, 1) { - copy(all(a), tree.begin() + n); + lazy(n, UF), h(__lg(2 * n)), k(2 * n, 1) { + ranges::copy(a, tree.begin() + n); for (int i = n - 1; i > 0; i--) { k[i] = 2 * k[2 * i]; tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - T comb(T a, T b) {return a + b;} // Modify this + E + T comb(T a, T b) { return a + b; } // Modify this + E void apply(int i, U val) { // And this + UF tree[i] = val * k[i]; @@ -44,17 +43,17 @@ struct SegTree { void update(int l, int r, U val) { l += n, r += n; int l0 = l, r0 = r; - push(l0), push(r0 - 1); + push(l0), push(r0); for (; l < r; l /= 2, r /= 2) { if (l&1) apply(l++, val); if (r&1) apply(--r, val); } - build(l0), build(r0 - 1); + build(l0), build(r0); } T query(int l, int r) { l += n, r += n; - push(l), push(r - 1); + push(l), push(r); T resL = E, resR = E; for (; l < r; l /= 2, r /= 2) { if (l&1) resL = comb(resL, tree[l++]); @@ -64,21 +63,23 @@ struct SegTree { } // Optional: - int lower_bound(int l, int r, T x) { + int binary_search(int l, int r, auto &&f) { + if (f(E)) return l; l += n, r += n; - push(l), push(r - 1); + push(l), push(r); int a[64] = {}, lp = 0, rp = 64; for (; l < r; l /= 2, r /= 2) { if (l&1) a[lp++] = l++; if (r&1) a[--rp] = --r; } - for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this + T x = E, y = x; + for (int i : a) if (i != 0 && f(x = comb(y = x, tree[i]))) { while (i < n) { push_down(i); - if (tree[2 * i] >= x) i = 2 * i; // And this - else i = 2 * i + 1; + if (f(x = comb(y, tree[2*i]))) i = 2 * i; + else i = 2 * i + 1, y = x; } - return i - n; + return i - n + 1; } return -1; } |