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

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

Depends on

Verified with

verify/yosupo/data-structure/area_of_union_of_rectangles.test.cpp

Code

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

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

template<class T>
struct MinCountAddAction{
    using InfoMonoid = MinCountMonoid<T>;
    using TagMonoid = AddMonoid<T>;
    using Info = typename InfoMonoid::value_type;
    using Tag = typename TagMonoid::value_type;
    static constexpr Info op(const Info &a,const Tag &b){
        if(a.first==InfoMonoid::unit().first)return a;
        return Info(a.first+b,a.second);
    }
};

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

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

template<class T>
struct AddMonoid{
    using value_type = T;
    static constexpr T op(const T &x,const T &y){return x+y;}
    static constexpr T inverse(const T &x){return -x;}
    static constexpr T unit(){return T(0);}
};

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

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

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

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

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

template<class T>
struct MinCountAddAction{
    using InfoMonoid = MinCountMonoid<T>;
    using TagMonoid = AddMonoid<T>;
    using Info = typename InfoMonoid::value_type;
    using Tag = typename TagMonoid::value_type;
    static constexpr Info op(const Info &a,const Tag &b){
        if(a.first==InfoMonoid::unit().first)return a;
        return Info(a.first+b,a.second);
    }
};