목차
5. BOJ16977 히스토그램에서 가장 큰 직사각형과 쿼리
BOJ8217 유성
PBS 문제이다. $x$ 일에 목표를 달성했다면 $x<y$인 임의의 $y$에 대해 $y$일에도 목표가 달성된 상태임이 보장된다. 따라서 매일의 운석 수를 빠르게 online으로 관리해주며 이분탐색 해주면 시간복잡도를 줄일 수 있다. 이때 매일의 운석 수를 빠르게 관리하는 것은 세그먼트 트리 혹은 펜윅 트리를 활용할 수 있는데, PBS 자체가 상수가 크게 붙는 경향이 있어 TLE를 피하려면 펜윅 트리를 사용하는 것이 정신 건강에 이로운 방법이다. 이를 구현하면 이분탐색 횟수가 최대 $O(\lg Q)$이고 모든 쿼리의 한 번의 이분탐색을 진행시키는 것은 $O(M\lg M+N)$이므로 총 $O((M\lg M+N)\lg Q)$에 문제를 해결할 수 있다.
BOJ16074 Mountaineers
최대 높이를 최소화하면서 특정 지점에서 다른 지점으로 도달할 때의 최대 높이를 묻는 문제이다. 최대 높이를 이분탐색으로 찾아주면 하나의 쿼리를 해결할 수 있고, 이를 PBS로 구현해주면 간단히 풀 수 있다. 이때 도달 가능 여부는 높이가 낮은 순으로 정점을 보면서 인접 정점이 최대 높이 제한을 넘지 않을 경우 disjoint set을 이용하여 같은 집합에 포함시켜줌으로써 간단하게 구할 수 있다.
BOJ5542 JOI 국가의 행사
Mountaineers와 굉장히 유사한 문제이다. 값을 최대화한다는 점과, multi-source dijkstra를 통해 정점에 직접 값을 부여해주어야 한다는 점을 제외하면 동일하다.
BOJ13361 최고의 대장장이 토르비욘
이 글의 6문제 중 유일하게 PBS를 사용하지 않는 문제이다. 최대 길이의 검을 만들기 위해서는 채택하지 않은 변의 길이를 최소화하면 된다. 이 값은 서로 같은 길이가 존재하는 두 사각형을 merge하여 같은 disjoint set에 존재하게끔 한 후, 각 disjoint set에 포함된 사각형의 수 k와 disjoint set에 포함된 사각형의 변의 길이 집합 S에 대해 S의 가장 작은 k의 서로 다른 길이를 합하면 구할 수 있다.
BOJ16977 히스토그램에서 가장 큰 직사각형과 쿼리
너비가 고정되어있으므로 최대 높이를 찾으면 최대 넓이가 된다. 이는 수열에서 값이 x 이상인 연속된 항의 최대 길이가 w 이상인가?의 결정 문제를 통한 파라메트릭 서치로 찾을 수 있다. 또한 이러한 쿼리는 가장 높은 높이를 갖는 위치부터 세그먼트 트리에서 1로 업데이트하며 연속된 1의 최대 길이를 구하는 세그먼트 트리로 만들어 쉽게 구할 수 있다. 이를 PBS로 구현하면 끝.
BOJ13208 승현이와 승현이
두 승현이의 상태를 묶어서 생각할 때, 총 상태의 개수는 최대 250000개이다. 즉 전체 상태와 그 상태간의 전이그래프는 25만개의 정점으로 구성되어있으며, 간선의 최대 개수는 $2NM$인 30만개로 추정할 수 있다. 따라서 이러한 그래프에서 두 상태가 연결되어있는지 판별하는 문제이므로, JOI 국가의 행사와 동일하게 풀어줄 수 있다.