Azberjibiou

Convex hull trick의 시간에 따른 관리

Convex Hull Trick의 시간에 따른 관리 Introduction Dynamic programming은 많은 문제에서 등장하는 풀이 방법이다. Convex hull trick은 $O(n^2)$ 시간복잡도를 $O(n log n)$으로 줄여주는 등 획기적인 시간 단축을 이루어내는 dynamic programming에 대한 최적화 방법이다. 이번 글에서는 시간에 따른 convex hull의 관리에 대해 알아본다. Persistent convex hull과 convex hull rollback에 대해서 알아보자. 1. Persistent Convex Hull 문제 상황 $n$개의 직선 $f_i(x) = a_ix + b_i$가 주어진다. 직선들의 기울기 $a_i$는 증가하는 순서로 주어진다. 쿼리로 주어진 $t$, $k$에 대해서...