library/algebra/lazy/AddSum.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/algebra/lazy/AddSum.hpp"

Depends on

Verified with

Code

#pragma once
#include "library/algebra/group/Add.hpp"
#include "library/algebra/group/CntSum.hpp"
template <typename X> struct LazyAddSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAdd<X>;
    using S = typename MX::value_type;
    static constexpr S mapping(const X &f, const S &x) {
        return {x.first + f * x.second, x.second};
    }
};

#line 2 "library/algebra/group/Add.hpp"
template<typename X>
struct GroupAdd {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr void Rchop(X&x, const X&y){ x+=y; }
  static constexpr void Lchop(const X&x, X&y){ y+=x; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "library/algebra/group/CntSum.hpp"
template <typename X> struct GroupCntSum {
    using P = std::pair<X, X>;
    using value_type = P;
    static constexpr P op(const P &x, const P &y) {
        return {x.first + y.first, x.second + y.second};
    }
    static constexpr void Rchop(P &x, const P &y) {
        x.first += y.first;
        x.second += y.second;
    }
    static constexpr void Lchop(const P &x, P &y) {
        y.first += x.first;
        y.second += x.second;
    }
    static constexpr P inverse(const P &x) { return {-x.fi, -x.se}; }
    static constexpr P unit() { return {0, 0}; }
    static constexpr bool commute = true;
};
template <typename X> std::vector<std::pair<X, X>> cnt_init(int n, const X &x) {
    return std::vector<std::pair<X, X>>(n, {x, 1});
}
template <typename X>
std::vector<std::pair<X, X>> cnt_init(const std::vector<X> &v) {
    int n = v.size();
    std::vector<std::pair<X, X>> res(n);
    for (int i = 0; i < n; i++)
        res[i] = {v[i], 1};
    return res;
}
#line 4 "library/algebra/lazy/AddSum.hpp"
template <typename X> struct LazyAddSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAdd<X>;
    using S = typename MX::value_type;
    static constexpr S mapping(const X &f, const S &x) {
        return {x.first + f * x.second, x.second};
    }
};