diff options
| author | MZuenni <michi.zuendorf@gmail.com> | 2024-06-28 13:47:18 +0200 |
|---|---|---|
| committer | MZuenni <michi.zuendorf@gmail.com> | 2024-06-28 13:47:18 +0200 |
| commit | 65d2ac37862ce9d1de208a05099c281863e66256 (patch) | |
| tree | d1fe1ece8790e8e8b2a8bcd3895f82477b3a0e2b /datastructures/lazyPropagation.cpp | |
| parent | a3c9198048cf465a3c01827b3667edfc99d8031c (diff) | |
| parent | 366ff0a4ba0c94f5cdc2cbd4e2c991ad0b544522 (diff) | |
merge
Diffstat (limited to 'datastructures/lazyPropagation.cpp')
| -rw-r--r-- | datastructures/lazyPropagation.cpp | 9 |
1 files changed, 4 insertions, 5 deletions
diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp index 7af1a6a..0fe7bbe 100644 --- a/datastructures/lazyPropagation.cpp +++ b/datastructures/lazyPropagation.cpp @@ -65,13 +65,12 @@ struct SegTree { ll lower_bound(int l, int r, T x) { l += n, r += n; push(l), push(r - 1); - vector<int> a, st; + int a[64] = {}, lp = 0, rp = 64; for (; l < r; l /= 2, r /= 2) { - if (l&1) a.push_back(l++); - if (r&1) st.push_back(--r); + if (l&1) a[lp++] = l++; + if (r&1) a[--rp] = --r; } - a.insert(a.end(), st.rbegin(), st.rend()); - for (int i : a) if (tree[i] >= x) { // Modify this + for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this while (i < n) { push_down(i); if (tree[2 * i] >= x) i = 2 * i; // And this |