hliu1alt's blog

By hliu1alt, history, 3 years ago, In English

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!

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)$$$.

»
12 months ago, # |
Rev. 4   Vote: I like it -7 Vote: I do not like it

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)$$$:

$$$l(r(x)) = l(\{ r_a × x_{sum} + x_{sz} × r_b, x_{sz} \}) = \{ l_a(r_a × x_{sum} + x_{sz} × r_b) + x_{sz} × l_b, x_{sz} \}$$$
$$$ = \{ (l_a × r_a) × x_{sum} + x_{sz} × (l_a × r_b + l_b), x_{sz} \}$$$
Code