Skip to content

Convex hull trick

c++

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
template<bool maximize=false>
struct ConvexHullTrick {
    using ll = long long;
    map<ll,ll> mp;

    void insert(ll a, ll b){
        if(maximize) a = -a, b = -b;

        if(mp.empty()){
            mp[a] = b;
            return;
        }
        else if(mp.size() == 1){
            if(mp.count(a)) chmin(mp[a], b);
            else mp[a] = b;
            return;
        }

        bool add = false;

        // 端
        if(a < (*mp.begin()).first or (*mp.rbegin()).first < a){
            mp[a] = b;
            add = true;
        }
        // 同じ傾きが存在
        else if(mp.count(a)){
            if(chmin(mp[a], b)) add = true;
        }
        else{
            pair<ll,ll> l = *mp.upper_bound(a), r = *mp.lower_bound(a);

            if(_judge(l, {a,b}, r)){
                mp[a] = b;
                add = true;
            }
        }

        if(add) remove(a);
        return;
    }

    void remove(ll a){
        // +
        {
            auto it = mp.lower_bound(a); ++it;

            while((*it).first != (*mp.rbegin()).first){
                --it;
                pair<ll,ll> l = *it;
                ++it;
                pair<ll,ll> m = *it;
                ++it;
                pair<ll,ll> r = *it;

                if(_judge(l,m,r)) break;

                mp.erase(m.first);
            }
        }
        // -
        {
            auto it = mp.upper_bound(a);
            while((*it).first != (*mp.begin()).first){
                ++it;
                pair<ll,ll> r = *it;
                --it;
                pair<ll,ll> m = *it;
                --it;
                pair<ll,ll> l = *it;

                if(_judge(l,m,r)) break;

                mp.erase(m.first);
            }
        }
        return;
    }

    bool _judge(pair<ll,ll> l, pair<ll,ll> m, pair<ll,ll> r){
        // mが必要 -> true
        ll a,b,al,bl,ar,br;
        tie(al,bl) = l; tie(a,b) = m; tie(ar,br) = r;

        return (a-al)*(br-bl) > (ar-al)*(b-bl);
    }

    ll query(ll x){
        if(mp.size() == 1){
            auto it = *mp.begin();
            ll a,b; tie(a,b) = it;
            return a*x + b;
        }

        auto itl = mp.begin(), itr = prev(mp.end());

        auto check = [&](){
            if(itl == itr) return false;
            itl++;
            ll p = (*itl).first, q = (*itr).first;
            itl--;
            return p != q;
        };

        while(check()){
            ll al,bl,ar,br; tie(al,bl) = *itl; tie(ar,br) = *itr;
            ll m = (al+ar)/2;
            auto it1 = mp.upper_bound(m);
            auto it0 = prev(it1);

            ll a0,b0,a1,b1; tie(a0,b0) = *it0; tie(a1,b1) = *it1;
            if(a0*x+b0 < a1*x+b1) itr = it0;
            else itl = it1;
        }

        ll al,bl,ar,br; tie(al,bl) = *itl; tie(ar,br) = *itr;
        ll ret = min(al*x+bl, ar*x+br);
        return ret;
    }
};