This documentation is automatically generated by online-judge-tools/verification-helper
#include "algebra/range_affine_range_sum.hpp"lazy_segtree<range_affine_range_sum<T>> のように使う。S = {T sum; int len}, F = monoid_affine<T>::S
from(v): 値 v 1 個分の要素 {v, 1} を返す。初期化や一点更新ではこれで S を作る。apply(l, r, {a, b}) で a[l], ..., a[r - 1] の各要素 x を a x + b にする。prod(l, r).sum が区間和。#pragma once
#include "algebra/monoid_affine.hpp"
template <class T>
struct range_affine_range_sum {
struct S {
T sum;
int len;
};
using F = typename monoid_affine<T>::S;
static S op(S a, S b) {
return {a.sum + b.sum, a.len + b.len};
}
static S e() {
return {T(0), 0};
}
static S mapping(F f, S x) {
return {f.a * x.sum + f.b * T(x.len), x.len};
}
static F composition(F f, F g) {
return monoid_affine<T>::op(g, f);
}
static F id() {
return monoid_affine<T>::e();
}
static constexpr bool composition_commutative = false;
static S from(T v) {
return {v, 1};
}
};#line 2 "algebra/monoid_affine.hpp"
template <class T>
struct monoid_affine {
struct S {
T a, b;
};
static S op(S f, S g) {
return {g.a * f.a, g.a * f.b + g.b};
}
static S e() {
return {T(1), T(0)};
}
static T eval(S f, T x) {
return f.a * x + f.b;
}
};
#line 3 "algebra/range_affine_range_sum.hpp"
template <class T>
struct range_affine_range_sum {
struct S {
T sum;
int len;
};
using F = typename monoid_affine<T>::S;
static S op(S a, S b) {
return {a.sum + b.sum, a.len + b.len};
}
static S e() {
return {T(0), 0};
}
static S mapping(F f, S x) {
return {f.a * x.sum + f.b * T(x.len), x.len};
}
static F composition(F f, F g) {
return monoid_affine<T>::op(g, f);
}
static F id() {
return monoid_affine<T>::e();
}
static constexpr bool composition_commutative = false;
static S from(T v) {
return {v, 1};
}
};