ConvexHullTrickSegmentTree - 非単調CHTセグメント木
(lib/16-convex-hull-trick/ConvexHullTrickSegmentTree.cpp)

• View this file on GitHub
• Last update: 2023-05-30 05:01:32+09:00

ConvexHullTrickSegmentTree

• セグ木にchtをのせたもの
• 内部でrbstを利用してるので、傾き、クエリの単調性がいらない

コンストラクタ

• ConvexHullTrickSegmentTree(const size_t num)
  • numの長さで確保する

メソッド

• update(size_t idx, const TypeValue a, const TypeValue b)
  • 区間[idx,idx+1)に直線ax+bを追加
  • $O(\log(N)^2)$
• get(int l, int r, TypeValue x)
  • 区間[l,r)におけるxにおける最大/最小値を取得
  • $O(\log(N)^2)$
• get_line(int l, int r, TypeValue x)
  • 区間[l,r)におけるxにおける最大/最小値をとる直線を取得
  • $O(\log(N)^2)$

参考資料

• Problem B
• I - Ramen

Code

/*
 * @title ConvexHullTrickSegmentTree - 非単調CHTセグメント木
 * @docs md/convex-hull-trick/ConvexHullTrickSegmentTree.md
 */
template<class Operator> class ConvexHullTrickSegmentTree {
    using TypeValue = typename Operator::TypeValue;
    using TypeNode = pair<TypeValue,TypeValue>;
    size_t length;
    size_t num;
    vector<ConvexHullTrick<Operator>> node;
public:
    inline constexpr TypeValue y(const TypeNode p, TypeValue x) {
        return p.first*x+p.second;
    }
    ConvexHullTrickSegmentTree(const size_t num): num(num) {
        for (length = 1; length <= num; length *= 2);
        node.resize(2 * length);
    }
    //[idx,idx+1) insert{ax+b}
    void update(size_t idx, const TypeValue a, const TypeValue b) {
        if(idx < 0 || length <= idx) return;
        for(idx+=length;idx;idx >>= 1) node[idx].insert(a,b);
    }
    //[l,r)
    TypeValue get(int l, int r, TypeValue x) {
        if (l < 0 || length <= l || r < 0 || length < r) return Operator::unit_value;
        TypeValue vl =  Operator::unit_value, vr = Operator::unit_value;
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) {
                auto tl=node[l++].get(x);
                vl = (Operator::func_compare(vl,tl)?vl:tl);
            }
            if(r&1) {
                auto tr=node[--r].get(x);
                vr = (Operator::func_compare(tr,vr)?tr:vr);
            }
        }
        return (Operator::func_compare(vl,vr)?vl:vr);
    }
    //[l,r)
    TypeNode get_line(int l, int r, TypeValue x) {
        if (l < 0 || length <= l || r < 0 || length < r) return {0,Operator::unit_value};
        TypeNode vl = {0,Operator::unit_value}, vr = {0,Operator::unit_value};
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) {
                auto tl=node[l++].get_line(x);
                vl = (Operator::func_compare(y(vl,x),y(tl,x))?vl:tl);
            }
            if(r&1) {
                auto tr=node[--r].get_line(x);
                vr = (Operator::func_compare(y(tr,x),y(vr,x))?tr:vr);
            }
        }
        return (Operator::func_compare(y(vl,x),y(vr,x))?vl:vr);
    }
    void print(){
        cout << "node" << endl;
        for(int i = 1,j = 1; i < 2*length; ++i) {
            node[i].print();
            if(i==((1<<j)-1) && ++j) cout << endl;
        }
    }
};

#line 1 "lib/16-convex-hull-trick/ConvexHullTrickSegmentTree.cpp"
/*
 * @title ConvexHullTrickSegmentTree - 非単調CHTセグメント木
 * @docs md/convex-hull-trick/ConvexHullTrickSegmentTree.md
 */
template<class Operator> class ConvexHullTrickSegmentTree {
    using TypeValue = typename Operator::TypeValue;
    using TypeNode = pair<TypeValue,TypeValue>;
    size_t length;
    size_t num;
    vector<ConvexHullTrick<Operator>> node;
public:
    inline constexpr TypeValue y(const TypeNode p, TypeValue x) {
        return p.first*x+p.second;
    }
    ConvexHullTrickSegmentTree(const size_t num): num(num) {
        for (length = 1; length <= num; length *= 2);
        node.resize(2 * length);
    }
    //[idx,idx+1) insert{ax+b}
    void update(size_t idx, const TypeValue a, const TypeValue b) {
        if(idx < 0 || length <= idx) return;
        for(idx+=length;idx;idx >>= 1) node[idx].insert(a,b);
    }
    //[l,r)
    TypeValue get(int l, int r, TypeValue x) {
        if (l < 0 || length <= l || r < 0 || length < r) return Operator::unit_value;
        TypeValue vl =  Operator::unit_value, vr = Operator::unit_value;
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) {
                auto tl=node[l++].get(x);
                vl = (Operator::func_compare(vl,tl)?vl:tl);
            }
            if(r&1) {
                auto tr=node[--r].get(x);
                vr = (Operator::func_compare(tr,vr)?tr:vr);
            }
        }
        return (Operator::func_compare(vl,vr)?vl:vr);
    }
    //[l,r)
    TypeNode get_line(int l, int r, TypeValue x) {
        if (l < 0 || length <= l || r < 0 || length < r) return {0,Operator::unit_value};
        TypeNode vl = {0,Operator::unit_value}, vr = {0,Operator::unit_value};
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) {
                auto tl=node[l++].get_line(x);
                vl = (Operator::func_compare(y(vl,x),y(tl,x))?vl:tl);
            }
            if(r&1) {
                auto tr=node[--r].get_line(x);
                vr = (Operator::func_compare(y(tr,x),y(vr,x))?tr:vr);
            }
        }
        return (Operator::func_compare(y(vl,x),y(vr,x))?vl:vr);
    }
    void print(){
        cout << "node" << endl;
        for(int i = 1,j = 1; i < 2*length; ++i) {
            node[i].print();
            if(i==((1<<j)-1) && ++j) cout << endl;
        }
    }
};

Back to top page