Lazy Segtree

モノイド $(S, \cdot: S \times S \to S, e \in S)$と、$S$ から $S$ への写像の集合 $F$ であって、以下の条件を満たすようなものについて使用できるデータ構造です。

• $F$ は恒等写像 $\mathrm{id}$ を含む。つまり、任意の $x \in S$ に対し $\mathrm{id}(x) = x$ をみたす。
• $F$ は写像の合成について閉じている。つまり、任意の $f, g \in F$ に対し $f \circ g \in F$ である。
• 任意の $f \in F, x, y \in S$ に対し $f(x \cdot y) = f(x) \cdot f(y)$ をみたす。

長さ $N$ の $S$ の配列に対し、

• 区間の要素に一括で $F$ の要素 $f$ を作用($x = f(x)$ )
• 区間の要素の総積の取得

を $O(\log N)$ で行うことが出来ます。詳細な要件は Appendix を参照してください。

また、このライブラリはオラクルとしてop, e, mapping, composition, idを使用しますが、これらが定数時間で動くものと仮定したときの計算量を記述します。オラクル内部の計算量が $O(f(n))$ である場合はすべての計算量が $O(f(n))$ 倍となります。

コンストラクタ

(1) var seg = initLazySegTree(n:int, op, e, mapping, composition, id)
    var seg = LazySegTreeType(S, F, op, e, mapping, composition, id).init(n)
    var seg = LazySegTree.getType(S, F, op, e, mapping, composition, id).init(n)
(2) var seg = initLazySegTree(v:seq[S], op, e, mapping, composition, id)
    var seg = LazySegTreeType(S, F, op, e, mapping, composition, id).init(v)
    var seg = LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v)

• モノイドの型 S
• $\cdot: S \times S \to S$ を計算する関数 S op(S a, S b)
• $e$ を返す関数 e():S
• 写像の型 F
• $f(x)$ を返す関数 mapping(f:F, x:S):S
• $f \circ g$ を返す関数 composition(f:F, f:F):F
• $id$ を返す関数 id():F

を定義する必要があります。 詳しくは、使用例や こちら も参照してください。

• (1): 長さ n の数列 a を作ります。初期値は全部e()です。
• (2): 長さ n = v.len の数列 a を作ります。v の内容が初期値となります。

制約

• $0 \leq n \leq 10^8$

計算量

• $O(n)$

set

seg.set(p:int, x:S):void
seg[p:int] = x:S

a[p] = x

制約

• $0 \leq p < n$

計算量

• $O(\log n)$

get

seg.get(p:int):S
seg[p:int]:S

a[p] を返します。

制約

• $0 \leq p < n$

計算量

• $O(\log n)$

prod

seg.prod(l..<r):S
seg[l..<r]:S

op(a[l], ..., a[r - 1]) を、モノイドの性質を満たしていると仮定して計算します。$l = r$ のときは e() を返します。

制約

• $0 \leq l \leq r \leq n$

計算量

• $O(\log n)$

all_prod

seg.all_prod():S

op(a[0], ..., a[n-1]) を計算します。$n = 0$ のときは e() を返します。

計算量

• $O(1)$

apply

(1) seg.apply(p:int, f:F):void
(2) seg.apply(l..<r, f:F):void

• (1) a[p] = f(a[p])
• (2) i = l..r-1についてa[i] = f(a[i])

制約

• (1) $0 \leq p < n$
• (2) $0 \leq l \leq r \leq n$

計算量

• $O(\log n)$

max_right

(1) seg.max_right(l:int, g:(S)->bool):int
(2💻) seg.max_right(l:int, g:(S)->bool):int

• (1): 関数 g(x:S):bool を定義する必要があります。segtreeの上で二分探索をします。
• (2): Sを引数にとりboolを返す関数オブジェクトを渡して使用します。

以下の条件を両方満たす r を(いずれか一つ)返します。

• r = l もしくは g(op(a[l], a[l + 1], ..., a[r - 1])) = true
• r = n もしくは g(op(a[l], a[l + 1], ..., a[r])) = false

gが単調だとすれば、g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r、と解釈することが可能です。

制約

• gを同じ引数で呼んだ時、返り値は等しい(=副作用はない)
• g(e()) = true
• $0 \leq l \leq n$

計算量

• $O(\log n)$

min_left

(1) seg.min_left(r:int, g:(S)->bool):int
(2💻) int seg.min_left(r:int, g:(S)->bool):int

• (1): 関数 bool g(S x) を定義する必要があります。segtreeの上で二分探索をします。
• (2): Sを引数にとりboolを返す関数オブジェクトを渡して使用します。

以下の条件を両方満たす l を(いずれか一つ)返します。

• l = r もしくは g(op(a[l], a[l + 1], ..., a[r - 1])) = true
• l = 0 もしくは g(op(a[l - 1], a[l], ..., a[r - 1])) = false

gが単調だとすれば、g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l、と解釈することが可能です。

制約

• gを同じ引数で呼んだ時、返り値は等しい(=副作用はない)
• g(e()) = true
• $0 \leq r \leq n$

計算量

• $O(\log n)$

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_k

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_l