Lazy Segtree

It is the data structure for the pair of a monoid $(S, \cdot: S \times S \to S, e \in S)$ and a set $F$ of $S \to S$ mappings that satisfies the following properties.

Given an array $S$ of length $N$, it processes the following queries in $O(\log N)$ time (see Appendix for further details).

For simplicity, in this document, we assume that the oracles op, e, mapping, composition, and id work in constant time. If these oracles work in $O(T)$ time, each time complexity appear in this document is multipled by $O(T)$.

Constructor

(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);

The following should be defined.

See examples and here for further details.

Constraints

Complexity

set

void seg.set(int p, S x)

a[p] = x

Constraints

Complexity

get

S seg.get(int p)

It returns a[p].

Constraints

Complexity

prod

S seg.prod(int l, int r)

It returns op(a[l], ..., a[r - 1]), assuming the properties of the monoid. It returns e() if $l = r$.

Constraints

Complexity

all_prod

S seg.all_prod()

It returns op(a[0], ..., a[n - 1]), assuming the properties of the monoid. It returns e() if $n = 0$.

Complexity

apply

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

Constraints

Complexity

max_right

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

It returns an index r that satisfies both of the followings.

If g is monotone, this is the maximum r that satisfies g(op(a[l], a[l + 1], ..., a[r - 1])) = true.

Constraints

Complexity

min_left

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

It returns an index l that satisfies both of the following.

If g is monotone, this is the minimum l that satisfies g(op(a[l], a[l + 1], ..., a[r - 1])) = true.

Constraints

Complexity

Examples

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); } } }