15955번: 부스터

시간 복잡도:

• $O(N \log N + Q \log N)$

알고리즘:

• MST
• 정렬
• LCA
• 희소 테이블

Figure 0. Background Knowledge

문제를 풀어서 해석해 봅시다. 우리가 알 수 있는 사실은 다음과 같습니다.

각 쿼리에서,

1. 체크포인트에 도달할 때마다 부스터를 채울 수 있습니다.
2. 그래서, 부스터를 포함한 체크포인트 간 이동 거리의 최댓값이 $X_i$ 미만이면 됩니다.