library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: Acted Monoid: Range Affine Range Sum
(algebra/range_affine_range_sum.hpp)

概要

使い方

Depends on

Verified with

Code

#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};
    }
};
Back to top page