Блог пользователя hliu1alt

Автор hliu1alt, история, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 месяцев назад, # |
Rev. 4   Проголосовать: нравится -7 Проголосовать: не нравится

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