콘텐츠로 이동

Convex Hull Trick

Problem

image 1

위 그림과 같이 문제 상황에 따라 min/max (최소/최대 쿼리), slope (삽입되는 직선들의 기울기 증가/감소), dir (삽입 직선들의 교점의 x좌표 증가/감소)이 결정된다.

  • Push : 일차함수 \(y=ax+b\)를 추가한다. 단, 삽입되는 기울기 \(a\)는 slope에 따라 증가하거나 감소해야 한다.
  • Query : 지금까지 추가된 일차함수들 중 특정 \(x\)에서의 함숫값들 중 min/max에 따라 최솟값 혹은 최댓값을 구한다.
  • Query2 : 지금까지 추가된 일차함수들 중 특정 \(x\)에서의 함숫값들 중 min/max에 따라 최솟값 혹은 최댓값을 구한다. 단, 쿼리로 주어지는 \(x\)는 dir에 따라 증가하거나 감소해야 한다.

Algorithm

  • Push

    최적의 직선들 (upper / lower convex hull)을 스택으로 관리한다. 이 때, dir이 증가한다면 cross(V[i-1], V[i]) < cross(V[i], V[i+1]), 감소한다면 cross(V[i-1], V[i]) > cross(V[i], V[i+1])을 강제한다. 새로운 직선을 추가할 때, 불변식을 만족시키지 않는 직선들을 스택의 위쪽에서 하나씩 제거한 후, 새로운 직선을 스택에 추가한다.

    Complexity

    ammortized \(O(1)\)

  • Query

    쿼리로 주어진 \(x\)를 이용하여 삽입된 직선들 사이의 교점들에 대한 이분탐색을 통해 최적의 직선을 찾고, 함숫값을 구한다.

    Complexity

    \(O(\log N)\)

  • Query2

    직선들의 교점이 삽입되는 방향 dir과 쿼리로 주어지는 \(x\)의 방향이 같으니, 한 번 최적해가 아닌 직선은 앞으로도 최적해가 될 수 없음을 이용한다. 직선들을 deque로 관리하여, 가장 앞의 교점과 \(x\)를 비교하여 최적이 아닌 직선을 하나씩 앞에서 제거한 후, 최적 함숫값을 구한다.

    Complexity

    Ammortized \(O(1)\)

Code

cht.cpp
 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
namespace CHT
{
    typedef __int128 dll;
    struct Line { ll a, b; };
    struct Frac
    {
        ll u, d;
        Frac(ll _u, ll _d) : u(_u), d(_d) { if(d<0) u=-u, d=-d; }
        bool operator < (const Frac &ot) const { return (dll)u*ot.d < (dll)ot.u*d; }
        bool operator > (const Frac &ot) const { return (dll)u*ot.d > (dll)ot.u*d; }
    };
    ll divfloor(ll u, ll d) { return u/d - ((u^d)<0 && u%d); }
    ll divceil(ll u, ll d) { return u/d + ((u^d)>0 && u%d); }

    // Get cross point of line p, q
    // If all queries are integer, change 'Frac' to 'div'
    Frac cross(const Line &p, const Line &q) { return Frac(p.b-q.b, q.a-p.a); } // dir + : divfloor, dir - : divceil

    // min/max : ?, slope : ?, dir : ?
    struct CHT
    {
        deque<Line> V;

        // Insert line p = ax+b
        // b must be increasing (or decreasing) ('slope')
        // cross(V[i-1], V[i]) < (or >) cross(V[i], V[i+1]) ('dir')
        void push(Line p)
        {
            if(!V.empty() && V.back().a==p.a)
            {
                if(V.back().b <= p.b) return; // min : <= , max : >=
                V.pop_back();
            }
            while(V.size()>1 && !(cross(V[V.size()-2], V[V.size()-1]) < cross(V[V.size()-1], p))) V.pop_back(); // dir + : <, dir - : >
            V.push_back(p);
        }

        // Get min (or max) value at x in O(logN)
        ll query(ll x)
        {
            assert(!V.empty());
            int lo=0, hi=V.size();
            while(lo+1<hi)
            {
                int mid=lo+hi>>1;
                if(cross(V[mid-1], V[mid]) < Frac(x, 1)) lo=mid; // dir + : <, dir - : >
                else hi=mid;
            }
            return V[lo].a*x+V[lo].b;
        }

        // Get min (or max) value at x in ammortized O(1)
        // x must be increasing (or decreasing) ('dir')
        ll query2(ll x)
        {
            assert(!V.empty());
            while(V.size()>1 && cross(V[0], V[1]) < Frac(x, 1)) V.pop_front(); // dir + : <, dir - : >
            return V[0].a*x+V[0].b;
        }
    };
}

Details

template
 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
namespace CHT
{
    typedef __int128 dll;
    struct Line { ll a, b; };
    struct Frac
    {
        ll u, d;
        Frac(ll _u, ll _d) : u(_u), d(_d) { if(d<0) u=-u, d=-d; }
        bool operator < (const Frac &ot) const { return (dll)u*ot.d < (dll)ot.u*d; }
        bool operator > (const Frac &ot) const { return (dll)u*ot.d > (dll)ot.u*d; }
    };
    ll divfloor(ll u, ll d) { return u/d - ((u^d)<0 && u%d); }
    ll divceil(ll u, ll d) { return u/d + ((u^d)>0 && u%d); }

    // min/max : ?, slope : ?, dir : ?
    struct CHT
    {
        // Get cross point of line p, q
        // If all queries are integer, change 'Frac' to 'div'
        Frac cross(const Line &p, const Line &q) { return Frac(p.b-q.b, q.a-p.a); } // dir + : divfloor, dir - : divceil
        deque<Line> V;

        // Insert line p = ax+b
        // b must be increasing (or decreasing) ('slope')
        // cross(V[i-1], V[i]) < (or >) cross(V[i], V[i+1]) ('dir')
        void push(Line p) {}

        // Get min (or max) value at x in O(logN)
        ll query(ll x) {}

        // Get min (or max) value at x in ammortized O(1)
        // x must be increasing (or decreasing) ('dir')
        ll query2(ll x) {}
    };
}
  • 문제 상황에 따라 min/max (최소/최대 쿼리), slope (삽입되는 직선들의 기울기 증가/감소), dir (삽입 직선들의 교점의 x좌표 증가/감소)이 결정된다.
  • Frac cross(const Line &p, const Line &q) {} : 두 직선의 교점의 x좌표를 Frac 자료형으로 리턴함
    • 모든 쿼리들이 정수라면, Frac 대신 dir이 증가한다면 divfloor, dir이 감소한다면 divceil으로 대체할 수 있음
  • void push(Line p) {} : 일차함수 \(y=ax+b\)를 추가함
    • 삽입되는 기울기 \(a\)는 slope에 따라 증가하거나 감소해야함
    • dir이 증가한다면 cross(V[i-1], V[i]) < cross(V[i], V[i+1]), 감소한다면 cross(V[i-1], V[i]) > cross(V[i], V[i+1])를 만족함
  • ll query(ll x) {} : 특정 \(x\)에서의 함숫값들 중 min/max에 따라 최솟값 혹은 최댓값을 리턴함
  • ll query2(ll x) {} : 특정 \(x\)에서의 함숫값들 중 min/max에 따라 최솟값 혹은 최댓값을 리턴함
    • 쿼리로 주어지는 \(x\)는 dir에 따라 증가하거나 감소해야 함
example
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void test_cht()
{
    // min/max : min, slope : -, dir : +
    CHT::CHT cht;

    cht.push({0, 1});
    cht.push({-1, -1});
    cht.push({-2, -1});

    assert(cht.query(-2) == 1);
    assert(cht.query(-1) == 0);
    assert(cht.query(0) == -1);
    assert(cht.query(1) == -3);

    assert(cht.query2(-2) == 1);
    assert(cht.query2(-1) == 0);
    assert(cht.query2(0) == -1);
    assert(cht.query2(1) == -3);
}