library/algebra/lazy/AffineSum.hpp

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

Depends on

Verified with

test/library-checker/DataStructure/RangeAffineRangeSum.test.cpp

Code

#pragma once
#include "library/algebra/group/Affine.hpp"
#include "library/algebra/group/CntSum.hpp"
template <typename X> struct LazyAffineSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAffine<X>;
    using P = typename MX::value_type;
    using F = typename MF::value_type;
    static constexpr P mapping(const F &f, const P &x) {
        return {f.a * x.first + f.b * x.second, x.second};
    }
};

#line 2 "library/linearalgebra/Linear.hpp"
template <typename T> struct Line {
    T a, b;
    Line() = default;
    Line(T a, T b) : a(a), b(b) {}
    Line(std::pair<T, T> l) : a(l.first), b(l.second) {}
    Line(T c) : a(0), b(c) {}

    T operator()(const T x) const { return a * x + b; }
    Line operator()(const Line &l) const { return Line(a * l.a, a * l.b + b); }

    bool operator==(const Line &l) const { return a == l.a and b == l.b; }
    bool operator!=(const Line &l) const { return !(*this == l); }
    bool operator<(const Line &l) const {
        return (a == l.a ? a < l.a : b < l.b);
    }

    Line &operator+=(const Line &l) {
        a += l.a;
        b += l.b;
        return *this;
    }
    Line operator+(const Line &l) const { return Line(*this) += l; }
    Line &operator-=(const Line &l) {
        a -= l.a;
        b -= l.b;
        return *this;
    }
    Line operator-(const Line &l) const { return Line(*this) -= l; }
    Line operator-() const { return Line(-a, -b); }

    Line &operator+=(const T &c) {
        b += c;
        return *this;
    }
    Line operator+(const T &c) const { return Line(*this) += c; }
    Line &operator-=(const T &c) {
        b -= c;
        return *this;
    }
    Line operator-(const T &c) const { return Line(*this) -= c; }
    Line &operator*=(const T &c) {
        a *= c;
        b *= c;
        return *this;
    }
    Line operator*(const T &c) const { return Line(*this) *= c; }
    Line &operator/=(const T &c) {
        a /= c;
        b /= c;
        return *this;
    }
    Line operator/(const T &c) const { return Line(*this) /= c; }

    Line inv() const {
        assert(a != 0);
        return Line(T(1) / a, -b / a);
    }

    friend std::istream &operator>>(std::istream &is, Line &l) {
        is >> l.a >> l.b;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Line &l) {
        if (l.a == 0 and l.b == 0)
            os << 0;
        else if (l.a == 0)
            os << l.b;
        else if (l.b == 0)
            os << l.a << "x";
        else if (l.b > 0)
            os << l.a << "x+" << l.b;
        else
            os << l.a << "x-" << -l.b;
        return os;
    }
};
#line 3 "library/algebra/group/Affine.hpp"
template <typename T> struct GroupAffine {
    using L = Line<T>;
    using value_type = L;
    static constexpr L op(const L &f, const L &g) noexcept { return f(g); }
    static constexpr void Rchop(L &f, const L &g) {
        f.b += f.a * g.b;
        f.a *= g.a;
    }
    static constexpr void Lchop(const L &f, L &g) {
        (g.b *= f.a) += f.b;
        g.a *= f.a;
    }
    static constexpr L inverse(const L &f) { return f.inv(); }
    /*
    static constexpr L power(const L& f,long long n) noexcept {
      if(a==1)return {1,n*b};
      K an=power(a,n);
      return {an,b*((1-an)/(1-a))};
    }
    */
    static constexpr L unit() { return L(1, 0); }
    static constexpr bool commute = false;
};
#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/AffineSum.hpp"
template <typename X> struct LazyAffineSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAffine<X>;
    using P = typename MX::value_type;
    using F = typename MF::value_type;
    static constexpr P mapping(const F &f, const P &x) {
        return {f.a * x.first + f.b * x.second, x.second};
    }
};