diff options
| -rw-r--r-- | TestMakefile | 8 | ||||
| -rw-r--r-- | datastructures/lazyPropagation.cpp | 19 | ||||
| -rw-r--r-- | datastructures/test/lazyPropagation.awk | 86 | ||||
| -rw-r--r-- | datastructures/test/lazyPropagation.cpp | 102 |
4 files changed, 205 insertions, 10 deletions
diff --git a/TestMakefile b/TestMakefile index ca1b2f8..5c46856 100644 --- a/TestMakefile +++ b/TestMakefile @@ -8,6 +8,8 @@ predep = $(patsubst $(source)=%,%,$(filter $(source)=%,$(PREDEPS))) TESTS := \ $(call with-defines-subsets,datastructures/test/segmentTree,SEGTREE_MUL SEGTREE_INIT_DEFAULT SEGTREE_RANGE_UPDATE) \ $(call with-defines-subsets,datastructures/test/segmentTree.SEGTREE_FIRST_NEG,SEGTREE_INIT_DEFAULT) \ + $(call with-defines-subsets,datastructures/test/lazyPropagation,SEGTREE_FIRST_NEG SEGTREE_INIT_DEFAULT) \ + $(call with-defines-subsets,datastructures/test/lazyPropagation.SEGTREE_MAX,SEGTREE_INIT_DEFAULT) \ datastructures/test/fenwickTree \ datastructures/test/fenwickTree2 \ datastructures/test/monotonicConvexHull \ @@ -20,7 +22,8 @@ TESTS := \ # Dependencies which must be present before generating the .d file. PREDEPS := \ - datastructures/test/segmentTree=datastructures/test/segmentTree.tmp.cpp + datastructures/test/segmentTree=datastructures/test/segmentTree.tmp.cpp \ + datastructures/test/lazyPropagation=datastructures/test/lazyPropagation.tmp.cpp CPPFLAGS := -include test.h -std=gnu++20 -Wall -Wextra \ -Werror -fsanitize=address,undefined -fno-sanitize-recover -g @@ -45,6 +48,9 @@ cleantest: datastructures/test/segmentTree.tmp.cpp: datastructures/segmentTree.cpp \ datastructures/test/segmentTree.awk awk -f datastructures/test/segmentTree.awk $< > $@ +datastructures/test/lazyPropagation.tmp.cpp: \ + datastructures/lazyPropagation.cpp datastructures/test/lazyPropagation.awk + awk -f datastructures/test/lazyPropagation.awk $< > $@ .PHONY: test cleantest .SECONDARY: $(TESTS:=.test) diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp index 7af1a6a..3d3ea6b 100644 --- a/datastructures/lazyPropagation.cpp +++ b/datastructures/lazyPropagation.cpp @@ -1,21 +1,22 @@ struct SegTree { using T = ll; using U = ll; - int n, h; static constexpr T E = 0; // Neutral element for combine static constexpr U UF = 0; // Unused value by updates + int n; vector<T> tree; vector<U> lazy; + int h; 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), //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]; @@ -42,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,7 +65,7 @@ struct SegTree { // Optional: ll lower_bound(int l, int r, T x) { l += n, r += n; - push(l), push(r - 1); + push(l), push(r); vector<int> a, st; for (; l < r; l /= 2, r /= 2) { if (l&1) a.push_back(l++); diff --git a/datastructures/test/lazyPropagation.awk b/datastructures/test/lazyPropagation.awk new file mode 100644 index 0000000..fc39305 --- /dev/null +++ b/datastructures/test/lazyPropagation.awk @@ -0,0 +1,86 @@ + +/Neutral element for combine/ { + print "#ifndef SEGTREE_FIRST_NEG" + print "# ifndef SEGTREE_MAX" + print + print "# else" + tmp = $0 + sub(/0/, "numeric_limits<T>::min()", tmp) + print tmp + print "# endif" + print "#else" + sub(/0/, "numeric_limits<T>::max()") + print + print "#endif" + next +} + +/Modify this \+ E/ { + print "#ifndef SEGTREE_FIRST_NEG" + print "# ifndef SEGTREE_MAX" + print + print "# else" + tmp = $0 + sub(/a \+ b/, "max(a, b)", tmp) + print tmp + print "# endif" + print "#else" + sub(/a \+ b/, "a < 0 ? a : min(a, b)") + print + print "#endif" + next +} + +/Unused value by updates/ { + print "#ifndef SEGTREE_FIRST_NEG" + print + print "#else" + sub(/0/, /numeric_limits<U>::max()/) + print + print "#endif" + next +} + +/And this \+ UF/ { + print + getline set_tree + getline set_lazy + print "#ifndef SEGTREE_MAX" + print "# ifndef SEGTREE_FIRST_NEG" + print set_tree + print "# else" + tmp = set_tree + sub(/val \* k\[i\]/, "val", tmp) + print tmp + print "# endif" + print set_lazy + print "#else" + sub(/= val \* k\[i\]/, "+= val", set_tree) + sub(/= val/, "+= val", set_lazy) + print set_tree + print set_lazy + print "#endif" + next +} + +/Optional/ { print "#ifdef SEGTREE_MAX" } +/^\};$/ { print "#endif" } + +/SegTree\(const vector<T>& a\)/ { + print "#ifndef SEGTREE_INIT_DEFAULT" + print + print "#else" + getline + sub(/\/\//, "") + print + print "#endif" + getline + print + print "#ifndef SEGTREE_INIT_DEFAULT" + getline + print + print "#endif" + next +} + +{ print } diff --git a/datastructures/test/lazyPropagation.cpp b/datastructures/test/lazyPropagation.cpp new file mode 100644 index 0000000..df97b14 --- /dev/null +++ b/datastructures/test/lazyPropagation.cpp @@ -0,0 +1,102 @@ +#include "lazyPropagation.tmp.cpp" + +void test(int n) { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a(n); + for (ll &x: a) x = util::randint(); + SegTree seg(a); +#else + ll init = util::randint(); +# ifdef SEGTREE_FIRST_NEG + init = abs(init); +# endif + vector<ll> a(n, init); + SegTree seg(n, init); +#endif + for (int i = 0; i < 5*n; i++) { + { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll v = util::randint(); +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + if (v == 0) v = 1; +# endif +#endif + for (int j = l; j < r; j++) { +#ifndef SEGTREE_MAX + a[j] = v; +#else + a[j] += v; +#endif + } + seg.update(l, r, v); + } + { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + ll comp = 0; +# else + ll comp = numeric_limits<ll>::min(); +# endif +#else + ll comp = numeric_limits<ll>::max(); +#endif + for (int j = l; j < r; j++) { +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + comp += a[j]; +# else + comp = max(comp, a[j]); +# endif +#else + if (comp >= 0 && comp > a[j]) comp = a[j]; +#endif + } + assert(seg.query(l, r) == comp); + } +#ifdef SEGTREE_MAX + { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll bound = util::randint(); + int found = -1; + for (int j = l; j < r; j++) { + if (a[j] >= bound) { + found = j; + break; + } + } + assert(seg.lower_bound(l, r, bound) == found); + } +#endif + } +} + +int main() { + test(1000); + test(1); + { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a; + SegTree seg(a); +#else + SegTree seg(0); +#endif + seg.update(0, 0, util::randint()); +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + assert(seg.query(0, 0) == 0); +# else + assert(seg.query(0, 0) == numeric_limits<ll>::min()); +# endif +#else + assert(seg.query(0, 0) == numeric_limits<ll>::max()); +#endif + } +} |