I've been trying to use the ACL lazy segtree (source code here) to solve the following CSES problem.
Is it possible through purely the template API? Or do I need to modify the internal implementation a bit. If it is possible, can anyone provide some hints on what values I need to be storing in S and what I need to pass around in F?
Thanks in advance!
It is possible, basically you express the lazy tag (
F
in the implementation) as a pair $$$(a, b)$$$ where you first assign all values in the range to $$$a$$$, then you add $$$b$$$ to all values. Also have some sentinel value for $$$a$$$ to indicate no range set operation (e.g. $$$0$$$). When you apply $$$(c, d)$$$ after $$$(a, b)$$$, the new lazy tag becomes $$$(c, d)$$$, and when you apply $$$(0, d)$$$ after $$$(a, b)$$$, it becomes $$$(a, b + d)$$$.Your task is to maintain an array $$$t(n)$$$, let's try to add query $$$0$$$:
$$$0.$$$ For each $$$i=[l,r]$$$ set $$$t_i←a×t_i$$$ + b.
$$$1.$$$ Increase each value in range $$$[l,r]$$$ by $$$x$$$.
$$$2.$$$ Set each value in range $$$[l,r]$$$ to $$$x$$$.
$$$3.$$$ Calculate the sum of values in range $$$[l,r]$$$.
Then the problem can be reduced to:
$$$0.$$$ For each $$$i=[l,r]$$$ set $$$t_i←a×t_i$$$ + b.
$$$1.$$$ Query $$$0$$$ with $$$(a, b) = (1, x)$$$.
$$$2.$$$ Query $$$0$$$ with $$$(a, b) = (0, x)$$$.
$$$3.$$$ Calculate the sum of values in range $$$[l,r]$$$.
This is known as Range Affine Range Sum, you can read the editorial here
We will define functions corresponding with atcoder lazysegtree document
$$$S\text{{sum, sz}}$$$ represents the sum of all elements and the sequence length.
$$$F\text{{a, b}}$$$ represents the form $$$f(x) = ax + b$$$
$$$op(S\ l, S\ r) = $$$ { $$$l_{sum} + r_{sum}, l_{sz} + r_{sz}$$$ }
$$$\text{e() = S{0, 0}}$$$ because $$$x + e = e + x$$$ for any $$$x ∈ S$$$
$$$id() = F$$$ { $$$1, 0$$$ } because $$$F$$$ contains an identity map given by $$$(a, b) = (1, 0) \to id(x) = ax + b = x$$$
$$$mapping(F\ l, S\ r) = S$$$ { $$$l_a × r_{sum} + r_{sz} × l_b, r_{sz}$$$ } because the sum will multiply by $$$a$$$ and increase by $$$sz × b$$$
$$$composition(F\ l, F\ r) = F$$$ { $$$l_a × r_a, l_a × r_b + l_b$$$ } because $$$F$$$ is closed under compositions. With $$$(F\ l, F\ r, S\ x)$$$: