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