diff options
| -rw-r--r-- | datastructures/lazyPropagation1.cpp | 16 | ||||
| -rw-r--r-- | datastructures/lazyPropagation2.cpp | 62 | ||||
| -rw-r--r-- | tcr.pdf | bin | 646588 -> 646379 bytes |
3 files changed, 41 insertions, 37 deletions
diff --git a/datastructures/lazyPropagation1.cpp b/datastructures/lazyPropagation1.cpp index 5f0049f..13359b3 100644 --- a/datastructures/lazyPropagation1.cpp +++ b/datastructures/lazyPropagation1.cpp @@ -1,5 +1,5 @@ int h; // = __lg(2*n) -//a value that is not used by the update query: +//a neutral value for the update: constexpr ll updateFlag = 0; vector<ll> d(N, updateFlag); @@ -9,13 +9,14 @@ void apply(int p, ll value) { } void build(int p) { + p >>= __builtin_ctzll(p); while (p > 1) { p/=2; tree[p] = max(tree[2*p], tree[2*p+1]) + d[p]; }} void push(int p) { - for (int s = h; s > 0; --s) { + for (int s = h; s > 0; s--) { int i = p >> s; if (d[i] != updateFlag) { apply(2*i , d[i]); @@ -23,22 +24,23 @@ void push(int p) { d[i] = updateFlag; }}} -void inc(int l, int r, ll value) { +void update(int l, int r, ll value) { // add value l += sz(tree)/2, r += sz(tree)/2; int l0 = l, r0 = r; - for (; l < r; l/=2, r/=2) { + for (; l < r; l /= 2, r /= 2) { if (l&1) apply(l++, value); if (r&1) apply(--r, value); } - build(l0); build(r0 - 1); + build(l0); + build(r0 - 1); } -ll query(int l, int r) { +ll query(int l, int r) { // max(l..r) l += sz(tree)/2, r += sz(tree)/2; push(l); push(r - 1); ll res = query_default; - for (; l < r; l/=2, r/=2) { + for (; l < r; l /= 2, r /= 2) { if (l&1) res = max(res, tree[l++]); if (r&1) res = max(tree[--r], res); } diff --git a/datastructures/lazyPropagation2.cpp b/datastructures/lazyPropagation2.cpp index e90c671..6529102 100644 --- a/datastructures/lazyPropagation2.cpp +++ b/datastructures/lazyPropagation2.cpp @@ -1,50 +1,52 @@ -void calc(int p, ll k) { - if (d[p] == updateFlag) tree[p] = tree[2*p] + tree[2*p+1]; - else tree[p] = d[p] * k; -} +int h; // = __lg(2*n) +//a value that is not used by the update query: +constexpr ll updateFlag = -1; +vector<ll> d(N, updateFlag); void apply(int p, ll value, int k) { tree[p] = value * k; if (p < sz(tree)/2) d[p] = value; } -void build(int l, int r) { - int k = 2; - for (l += sz(tree)/2, r += sz(tree)/2-1; l > 1; k <<= 1) { - l/=2, r/=2; - for (int i = r; i >= l; --i) calc(i, k); +void build(int p) { + p >>= __builtin_ctzll(p); + for (int k = 2; p > 1; k <<= 1) { + p/=2; + if (d[p] == updateFlag) tree[p] = tree[2*p] + tree[2*p+1]; + else tree[p] = d[p] * k; }} -void push(int l, int r) { - int s = h, k = 1 << (h-1); - for (l += sz(tree)/2, r += sz(tree)/2-1; s > 0; --s, k/=2) { - for (int i = l >> s; i <= r >> s; ++i) { - if (d[i] != updateFlag) { - apply(2*i , d[i], k); - apply(2*i+1, d[i], k); - d[i] = updateFlag; -}}}} +void push(int p) { + for (int s = h, k = 1 << (h-1); s > 0; s--, k/=2) { + int i = p >> s; + if (d[i] != updateFlag) { + apply(2*i , d[i], k); + apply(2*i+1, d[i], k); + d[i] = updateFlag; +}}} -void modify(int l, int r, ll value) { +void update(int l, int r, ll value) { // assign value if (value == updateFlag) return; - push(l, l + 1); - push(r - 1, r); + l += sz(tree)/2, r += sz(tree)/2; + push(l); + push(r - 1); int l0 = l, r0 = r, k = 1; - for (l += sz(tree)/2, r += sz(tree)/2; l<r; l/=2, r/=2, k*=2) { + for (; l < r; l /= 2, r /= 2, k *= 2) { if (l&1) apply(l++, value, k); if (r&1) apply(--r, value, k); } - build(l0, l0 + 1); - build(r0 - 1, r0); + build(l0); + build(r0 - 1); } -ll query(int l, int r) { - push(l, l + 1); - push(r - 1, r); +ll query(int l, int r) { // sum(l..r) + l += sz(tree)/2, r += sz(tree)/2; + push(l); + push(r - 1); ll res = query_default; - for (l += sz(tree)/2, r += sz(tree)/2; l < r; l/=2, r/=2) { - if (l&1) res += tree[l++]; - if (r&1) res += tree[--r]; + for (; l < r; l /= 2, r /= 2) { + if (l&1) res = res + tree[l++]; + if (r&1) res = tree[--r] + res; } return res; } Binary files differ |