콘텐츠로 이동

볼록 껍질 트릭과 Li Chao 트리

다음 문제를 생각해 봅시다. $n$개의 도시가 있습니다. 여러분은 자동차로 도시 $1$에서 도시 $n$까지 이동하려고 합니다. 이를 위해서는 휘발유를 구입해야 합니다. $k^{th}$ 도시에서 휘발유 1리터의 가격은 $cost_k$임이 알려져 있습니다. 처음에 연료 탱크는 비어 있으며, 1킬로미터당 휘발유 1리터를 소비합니다. 도시들은 같은 직선 위에 오름차순으로 위치하며, $k^{th}$ 도시의 좌표는 $x_k$입니다. 또한 $k^{th}$ 도시에 들어가려면 $toll_k$를 지불해야 합니다. 여러분의 과제는 가능한 최소 비용으로 여행을 마치는 것입니다. 해답을 동적 계획법으로 계산할 수 있다는 것은 자명합니다:

$$dp_i = toll_i+\min\limits_{j<i}(cost_j \cdot (x_i - x_j)+dp_j)$$

단순한 접근법은 $O(n^2)$의 복잡도를 가지며, 이는 $O(n \log n)$ 또는 $O(n \log [C \varepsilon^{-1}])$로 개선할 수 있습니다. 여기서 $C$는 $|x_i|$가 가질 수 있는 최댓값이고, $\varepsilon$은 $x_i$를 다루는 정밀도입니다(보통 그렇듯이 정수인 경우에는 $\varepsilon = 1$입니다). 이를 위해서는 이 문제가 집합에 일차 함수 $k \cdot x + b$를 추가하고 특정 지점 $x$에서 함수들의 최솟값을 구하는 문제로 환원될 수 있다는 점에 주목해야 합니다. 여기서 사용할 수 있는 주요 접근법은 두 가지입니다.

볼록 껍질 트릭

이 접근법의 아이디어는 일차 함수들의 아래쪽 볼록 껍질을 유지하는 것입니다. 사실 이들을 일차 함수가 아니라 평면 위의 점 $(k;b)$로 생각하는 편이 조금 더 편리합니다. 그러면 주어진 점 $(x;1)$과의 내적이 가장 작은 점을 찾아야 하는데, 이는 곧 그 점에 대해 $kx+b$가 최소화된다는 뜻이므로 원래 문제와 같습니다. 아래에서 볼 수 있듯이, 이러한 최솟값은 반드시 이 점들의 아래쪽 볼록 포락선 위에 있습니다:

lower convex hull

볼록 껍질 위의 점들과 껍질 간선들의 법선 벡터를 저장해야 합니다. $(x;1)$ 쿼리가 주어지면 그것과 이루는 각도가 가장 가까운 법선 벡터를 찾아야 하며, 그러면 최적의 일차 함수는 그 간선의 끝점 중 하나에 대응합니다. 이를 확인하려면, $(x;1)$과의 내적이 상수인 점들은 $(x;1)$에 수직인 직선 위에 놓인다는 점에 주목해야 합니다. 따라서 최적의 일차 함수는 $(x;1)$의 법선과 평행한 볼록 껍질의 접선이 껍질에 닿는 점에 해당하는 함수입니다. 이 점은 그 왼쪽과 오른쪽에 있는 간선들의 법선이 $(x;1)$을 기준으로 서로 다른 쪽을 향하는 점입니다.

이 접근법은 일차 함수를 추가하는 쿼리가 $k$에 대해 단조적이거나, 오프라인으로 작업하는 경우, 즉 모든 일차 함수를 먼저 추가한 뒤 나중에 쿼리에 답할 수 있는 경우에 유용합니다. 따라서 이 방법으로는 도시/휘발유 문제를 풀 수 없습니다. 그 문제는 온라인 쿼리를 처리해야 하기 때문입니다. 그러나 온라인 쿼리를 처리해야 하는 경우에는 상황이 까다로워지며, 올바른 볼록 껍질을 구현하기 위해 일종의 set 자료 구조를 사용해야 합니다. 그러나 온라인 접근법은 어렵기도 하고, 두 번째 접근법(Li Chao 트리)으로 문제를 훨씬 간단하게 풀 수 있기 때문에 이 글에서는 다루지 않습니다. 제곱근 분할을 사용하면 이 접근법을 복잡한 처리 없이 온라인으로도 사용할 수 있다는 점은 언급할 만합니다. 즉, 새 직선이 $\sqrt n$개 추가될 때마다 볼록 껍질을 처음부터 다시 구축합니다.

이 접근법을 구현하려면 몇 가지 기하 유틸리티 함수부터 시작해야 하며, 여기서는 C++의 복소수 타입을 사용할 것을 제안합니다.

typedef int ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype cross(point a, point b) {
    return (conj(a) * b).y();
}

여기서는 일차 함수가 추가될 때 그 $k$가 증가하기만 하며, 최솟값을 구하려 한다고 가정하겠습니다. 껍질의 점들은 벡터 $hull$에, 법선 벡터들은 벡터 $vecs$에 저장하겠습니다. 새로운 점을 추가할 때는 볼록 껍질의 마지막 간선과, 볼록 껍질의 마지막 점에서 새로운 점으로 향하는 벡터가 이루는 각을 살펴보아야 합니다. 이 각은 반시계 방향이어야 합니다. 즉, 껍질의 마지막 법선 벡터(껍질 안쪽을 향하는 벡터)와 마지막 점에서 새로운 점으로 향하는 벡터의 내적이 음수가 아니어야 합니다. 이 조건이 성립하지 않는 동안에는 볼록 껍질의 마지막 점을 그에 대응하는 간선과 함께 지워야 합니다.

vector<point> hull, vecs;

void add_line(ftype k, ftype b) {
    point nw = {k, b};
    while(!vecs.empty() && dot(vecs.back(), nw - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
    }
    if(!hull.empty()) {
        vecs.push_back(1i * (nw - hull.back()));
    }
    hull.push_back(nw);
}
이제 어떤 점에서의 최솟값을 구하려면, 볼록 껍질에서 $(x;1)$로부터 반시계 방향에 있는 첫 번째 법선 벡터를 찾습니다. 그러한 간선의 왼쪽 끝점이 답이 됩니다. 벡터 $a$가 벡터 $b$로부터 반시계 방향에 있지 않은지 확인하려면, 두 벡터의 외적 $[a,b]$가 양수인지 확인하면 됩니다. 
int get(ftype x) {
    point query = {x, 1};
    auto it = lower_bound(vecs.begin(), vecs.end(), query, [](point a, point b) {
        return cross(a, b) > 0;
    });
    return dot(query, hull[it - vecs.begin()]);
}

Li Chao 트리

어느 두 함수든 많아야 한 번만 교차하는 함수들의 집합이 주어졌다고 가정합시다. 세그먼트 트리의 각 정점에 어떤 함수를 저장하되, 루트에서 리프까지 내려가면 경로에서 만난 함수 중 하나가 반드시 그 리프에서 최솟값을 주는 함수가 되도록 저장합시다. 이를 어떻게 구성하는지 살펴봅시다.

반열린 구간 $[l,r)$에 대응하는 어떤 정점에 있고, 그곳에 함수 $f_{old}$가 저장되어 있으며, 함수 $f_{new}$를 추가한다고 가정합시다. 그러면 교점은 $[l;m)$ 또는 $[m;r)$ 중 한 곳에 있게 됩니다. 여기서 $m=\left\lfloor\tfrac{l+r}{2}\right\rfloor$입니다. 이는 점 $l$과 $m$에서 두 함수의 값을 비교하여 효율적으로 알아낼 수 있습니다. 우세한 함수가 바뀐다면 교점은 $[l;m)$에 있고, 그렇지 않다면 $[m;r)$에 있습니다. 이제 교점이 없는 쪽 절반 구간에 대해서는 더 낮은 함수를 골라 현재 정점에 기록합니다. 이 함수는 항상 점 $m$에서 더 낮은 함수임을 알 수 있습니다. 그다음 더 높았던 함수를 가지고 구간의 나머지 절반으로 재귀적으로 내려갑니다. 보시다시피 이렇게 하면 구간의 첫 번째 절반에서는 정확성이 유지되고, 나머지 절반에서는 재귀 호출 과정에서 정확성이 유지됩니다. 따라서 함수를 추가하고 한 점에서의 최솟값을 확인하는 작업을 $O(\log [C\varepsilon^{-1}])$에 수행할 수 있습니다.

다음은 새로운 함수를 추가할 때 정점에서 일어나는 일을 나타낸 그림입니다:

Li Chao Tree vertex

이제 구현으로 넘어갑시다. 이번에도 일차 함수를 저장하기 위해 복소수를 사용하겠습니다.

typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype f(point a,  ftype x) {
    return dot(a, {x, 1});
}
함수들은 배열 $line$에 저장하고, 세그먼트 트리에는 이진 인덱싱을 사용하겠습니다. 큰 수나 double 값에 대해 사용하려면 동적 세그먼트 트리를 사용해야 합니다. 세그먼트 트리는 기본값, 예를 들어 직선 $0x + \infty$로 초기화해야 합니다.

const int maxn = 2e5;

point line[4 * maxn];

void add_line(point nw, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(line[v], l);
    bool mid = f(nw, m) < f(line[v], m);
    if(mid) {
        swap(line[v], nw);
    }
    if(r - l == 1) {
        return;
    } else if(lef != mid) {
        add_line(nw, 2 * v, l, m);
    } else {
        add_line(nw, 2 * v + 1, m, r);
    }
}
이제 어떤 점 $x$에서의 최솟값을 구하려면, 그 점까지의 경로를 따라가며 최솟값을 고르기만 하면 됩니다. 
ftype get(int x, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    if(r - l == 1) {
        return f(line[v], x);
    } else if(x < m) {
        return min(f(line[v], x), get(x, 2 * v, l, m));
    } else {
        return min(f(line[v], x), get(x, 2 * v + 1, m, r));
    }
}

문제