BOJ 6297 Intervals

이 문제는 가능한 한 뒤쪽의 수를 선택하는 그리디로 풀 수 있습니다.

$a_i$, $b_i$, $c_i$가 있으면 반드시 선택해야 하는 가장 작은 수는 $k = b_i - c_i + 1$이 되며, 이들 중 가장 작은 것을 $Z$에 넣는 행동을 반복하면 됩니다. 이러한 행동을 하고 나면, $k$를 포함하는 모든 구간의 $c_i$를 1 감소, 다르게 생각하면 그 구간의 최소 선택지를 1 증가시켜야 하며, 더이상 고려할 필요가 없는 구간은 제외하여야 합니다.

이는 구간 덧셈 업데이트, 구간 최솟값 쿼리를 수행하는 레이지 세그먼트 트리를 사용하여 관리할 수 있습니다. 먼저 모든 구간들을 $a_i$의 증가순으로 정렬하면 업데이트를 하나의 구간 업데이트로 만들 수 있습니다. 그리고 제외할 구간은 최소 힙을 사용하여 관리할 수 있는데, 구간이 추가될 때 언제 구간을 제거하면 되는지를 가지고 힙에 추가하고, 각 수가 선택될 때마다 횟수가 모두 소진된 구간들을 모두 제거해주면 됩니다.