library/algebra/lazy/SetSum.hpp

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

Depends on

Verified with

test/AOJ/DSL_2_I.test.cpp

Code

#pragma once
#include "library/algebra/group/CntSum.hpp"
#include "library/algebra/monoid/Set.hpp"
template <typename X> struct LazySetSum {
    using MX = GroupCntSum<X>;
    using MF = MonoidSet<X>;
    using P = typename MX::value_type;
    using F = typename MF::value_type;
    static constexpr P mapping(const F &f, const P &x) {
        if (f.has_value())
            return {f.value() * x.second, x.second};
        return x;
    }
};

#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 2 "library/algebra/monoid/Set.hpp"
// 合成の順番は関数と一緒だよ
template <typename X> struct MonoidSet {
    using O = std::optional<X>;
    using value_type = O;
    static constexpr O op(const O &x, const O &y) noexcept {
        return (x.has_value() ? x : y);
    }
    static constexpr void Rchop(O &x, const O &y) {
        if (!x)
            x = y;
    }
    static constexpr void Lchop(const O &x, O &y) {
        if (x)
            y = x;
    }
    static constexpr O unit() noexcept { return std::nullopt; }
    static constexpr bool commute = false;
};
#line 4 "library/algebra/lazy/SetSum.hpp"
template <typename X> struct LazySetSum {
    using MX = GroupCntSum<X>;
    using MF = MonoidSet<X>;
    using P = typename MX::value_type;
    using F = typename MF::value_type;
    static constexpr P mapping(const F &f, const P &x) {
        if (f.has_value())
            return {f.value() * x.second, x.second};
        return x;
    }
};