[백준] 20933. 마스크펑크 2077

https://www.acmicpc.net/problem/20933

문제요약

• 지점별 마스크의 가격과, 지점간 이동 시간이 주어짐 (N = 10만)
• 두 가지 쿼리를 수행
  • 특정 지점에서 시간 x로 이동할 수 있는 지점 중 최소 마스크 가격
  • 특정 지점간 이동시간을 변경

접근법

• 특정 지점에서 시간 t로 이동할 수 있는 지점을 어떻게 찾을까?
  • 누적합으로 이용해도 되겠지만 이동시간 변경에 대응이 안됨
  • 특정 지점간 이동 시간은 ${logN}$으로 구간합은 구해볼 수 있겠으니 (구간트리 이용)
  • 지점에서 멀어질수록 구간합은 증가할 것이고..... 이분탐색 이용 가능 : ${logN * logN}$
    • 지점을 변경해가며 t보다 큰지 작은지 비교해가면서
    • 다만 구간이 주어지는 방식이 ${(x_i, x_{i+1}) => x_i}$ 로 주어지므로 왼쪽 오른쪽 인덱스처리는 주의해서 해야함
• 특정 지점의 왼쪽/오른쪽 한계를 알면...그 사이의 최소값은 구간트리를 이용하면 구해볼 수 있겠음
• 시간복잡도
  • 최소값 찾기 : ${O(logN)}$
  • 지점간 이동시간 합 구하기 : ${O(logN)}$
  • 쿼리당 이분탐색 횟수 : ${O(2 * logN)}$
  • 입력/구간트리 생성 + 쿼리 x (이분탐색 x 이동시간 + 최소값구하기)
  • ${O(N + Q * (logN * logN + logN)) = O(Q*(logN)^2)}$