Lazy Segtree

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

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

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

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

コンストラクタ

(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);

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

制約

計算量

set

void seg.set(int p, S x)

a[p] = x

制約

計算量

get

S seg.get(int p)

a[p] を返します。

制約

計算量

prod

S seg.prod(int l, int r)

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

制約

計算量

all_prod

S seg.all_prod()

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

計算量

apply

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

制約

計算量

max_right

(1) int seg.max_right<g>(int l)
(2💻) int seg.max_right<G>(int l, G g)

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

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

制約

計算量

min_left

(1) int seg.min_left<g>(int r)
(2💻) int seg.min_left<G>(int r, G g)

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

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

制約

計算量

使用例

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

#include <atcoder/lazysegtree> #include <atcoder/modint> #include <cstdio> using namespace std; using namespace atcoder; using mint = modint998244353; struct S { mint a; int size; }; struct F { mint a, b; }; S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; } S e() { return S{0, 0}; } S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; } F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; } F id() { return F{1, 0}; } int main() { int n, q; scanf("%d %d", &n, &q); vector<S> a(n); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); a[i] = S{x, 1}; } lazy_segtree<S, op, e, F, mapping, composition, id> seg(a); for (int i = 0; i < q; i++) { int t; scanf("%d", &t); if (t == 0) { int l, r; int c, d; scanf("%d %d %d %d", &l, &r, &c, &d); seg.apply(l, r, F{c, d}); } else { int l, r; scanf("%d %d", &l, &r); printf("%d\n", seg.prod(l, r).a.val()); } } }

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

#include <atcoder/lazysegtree> #include <atcoder/modint> #include <cstdio> using namespace std; using namespace atcoder; using mint = modint998244353; struct S { // # of 0 / # of 1 / inversion number long long zero, one, inversion; }; // swapping flag using F = bool; S op(S l, S r) { return S{ l.zero + r.zero, l.one + r.one, l.inversion + r.inversion + l.one * r.zero, }; } S e() { return S{0, 0, 0}; } S mapping(F l, S r) { if (!l) return r; // swap return S{r.one, r.zero, r.one * r.zero - r.inversion}; } F composition(F l, F r) { return (l && !r) || (!l && r); } F id() { return false; } int main() { int n, q; scanf("%d %d", &n, &q); vector<S> a(n); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); if (x == 0) a[i] = S{1, 0, 0}; else a[i] = S{0, 1, 0}; } lazy_segtree<S, op, e, F, mapping, composition, id> seg(a); for (int i = 0; i < q; i++) { int t, l, r; scanf("%d %d %d", &t, &l, &r); l--; if (t == 1) { seg.apply(l, r, true); } else { printf("%lld\n", seg.prod(l, r).inversion); } } }