BOJ 26970 - Mountains

BOJ 26970 - Mountains

$(i, h_i)$ 에서 오른쪽으로 볼 수 있는 $(j, h_j)$ 들의 집합을 관리한다.

이 집합에서 항상 $\dfrac{h_j-h_i}{j-i} \le \dfrac{h_{j+1}-h_i}{j+1-i}$ 임을 관찰한다.

따라서 std::set 으로 이 집합들을 관리해주며 $O(qn \log n)$ 에 문제를 해결할 수 있다.

항상 $h$는 추가가 되기 때문에 다음과 같은 방식이 성립한다.

$h_i$ 가 추가되었다고 하자.

$j <i$ 라면 $i \in S_j$ 라면 $S_j$ 에서 $i$를 제거하고 $S_j$ 에서 $i$ 초과의 수들 중 $i$가 커짐으로써 안보이게 되는 것들을 모두 제거한다음 $i$ 가 $S_j$ 에서 보인다면 삽입해준다.

$S_i$는 초기화하고 다시 $O(n \log n)$으로 보이는 것들을 다 넣어준다.

$j > i$ 라면 신경 쓸 필요 없다.

따라서 이렇게 관리하여 문제를 해결할 수 있다.

bitset 을 이용한 최적화도 가능한 모양이다.