This documentation is automatically generated by online-judge-tools/verification-helper
#include "algebra/monoid_max_subarray_sum.hpp"segtree<monoid_max_subarray_sum<T>> のように使う。S = {T sum, max_prefix, max_suffix, max_subarray}from(v): 値 v 1 個分の要素を返す。初期化や一点更新ではこれで S を作る。prod(l, r).max_subarray が a[l], ..., a[r - 1] の空でない連続部分列の和の最大値。$l = r$ なら std::numeric_limits<T>::lowest()。#pragma once
#include <algorithm>
#include <limits>
template <class T>
struct monoid_max_subarray_sum {
struct S {
T sum, max_prefix, max_suffix, max_subarray;
};
static S op(S a, S b) {
if (a.max_subarray == ninf) return b;
if (b.max_subarray == ninf) return a;
return {a.sum + b.sum, std::max(a.max_prefix, a.sum + b.max_prefix), std::max(b.max_suffix, a.max_suffix + b.sum),
std::max({a.max_subarray, b.max_subarray, a.max_suffix + b.max_prefix})};
}
static S e() {
return {T(0), ninf, ninf, ninf};
}
static S from(T v) {
return {v, v, v, v};
}
private:
static constexpr T ninf = std::numeric_limits<T>::lowest();
};#line 2 "algebra/monoid_max_subarray_sum.hpp"
#include <algorithm>
#include <limits>
template <class T>
struct monoid_max_subarray_sum {
struct S {
T sum, max_prefix, max_suffix, max_subarray;
};
static S op(S a, S b) {
if (a.max_subarray == ninf) return b;
if (b.max_subarray == ninf) return a;
return {a.sum + b.sum, std::max(a.max_prefix, a.sum + b.max_prefix), std::max(b.max_suffix, a.max_suffix + b.sum),
std::max({a.max_subarray, b.max_subarray, a.max_suffix + b.max_prefix})};
}
static S e() {
return {T(0), ninf, ninf, ninf};
}
static S from(T v) {
return {v, v, v, v};
}
private:
static constexpr T ninf = std::numeric_limits<T>::lowest();
};