group/monoid-action/add-count-affine.hpp

• View this file on GitHub
• Last update: 2024-06-10 17:34:10+07:00
• Include: #include "group/monoid-action/add-count-affine.hpp"

Depends on

• group/monoid/add-count.hpp
• group/monoid/affine.hpp

Verified with

• verify/yosupo/data-structure/dynamic_sequence_range_affine_range_sum.test.cpp
• verify/yosupo/data-structure/range_affine_range_sum.test.cpp
• verify/yosupo/data-structure/range_affine_range_sum_lct.test.cpp

Code

#pragma once
#include "group/monoid/affine.hpp"
#include "group/monoid/add-count.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Affine to Add & Count Action class.
 */

template<class T>
struct AddCountAffineAction{
    using InfoMonoid = AddCountMonoid<T>;
    using TagMonoid = AffineMonoid<T>;
    using Info = typename InfoMonoid::value_type;
    using Tag = typename TagMonoid::value_type;
    static constexpr Info op(const Info &a,const Tag &b){
        return Info(a.first*b.first+a.second*b.second,a.second);
    }
};

#line 2 "group/monoid/affine.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Affine Transfomation Monoid class.
 */

template<class T>
struct AffineMonoid{
    using P = pair<T,T>;
    using value_type = P;
    static constexpr P op(const P &x,const P &y){
        return P(x.first*y.first,x.second*y.first+y.second);
    }
    static constexpr P unit(){return P(T(1),T(0));}
    static constexpr T eval(const P &f,const T &x){
        return f.first*x+f.second;
    }
};

#line 2 "group/monoid/add-count.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Add & Count Monoid class.
 */

template<class T>
struct AddCountMonoid{
    using P = pair<T,int>;
    using value_type = P;
    static constexpr P op(const P &x,const P &y){
        return P(x.first+y.first,x.second+y.second);
    }
    static constexpr P inverse(const P &x){return P(-x.first,-x.second);}
    static constexpr P unit(){return P(T(0),0);}
    static constexpr P make(const T &x){return P(x,1);}
};

#line 4 "group/monoid-action/add-count-affine.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Affine to Add & Count Action class.
 */

template<class T>
struct AddCountAffineAction{
    using InfoMonoid = AddCountMonoid<T>;
    using TagMonoid = AffineMonoid<T>;
    using Info = typename InfoMonoid::value_type;
    using Tag = typename TagMonoid::value_type;
    static constexpr Info op(const Info &a,const Tag &b){
        return Info(a.first*b.first+a.second*b.second,a.second);
    }
};

Back to top page