[BOJ] 14427 수열과 쿼리 15

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

14427번: 수열과 쿼리 15

알고리즘: Segment tree

 

시간복잡도: $O((M+N)logN)$

---

접근:

1. 많은 수의 쿼리 ($1\le M\le 10^5$)

 

일단 쿼리 수가 너무 많다는 점에서 나이브한 방법으로는 안된다는 걸 알 수 있다.

 

매 쿼리마다 최솟값을 구하다 보면 시간복잡도가 $O(MN)$이 나와 TLE를 받게 된다.

지금보니 쿼리가 구간 쿼리가 아니여서 naive하게 구현해도 될 듯 싶다. (priority queue 등)

 

고로 매 순간마다 쿼리를 계산하는게 아니라,

미리 전처리를 한 데이터를 가지고 쿼리를 빠른 속도로 계산하는 방식으로 접근해야 한다.

그리고 이런 유형의 문제에서 강력한 도구가 바로 트리 구조이다.

 

문제를 해결할 수 있는 다양한 트리구조가 있는데 그 중 segment tree를 사용하여 문제를 해결하였다.

(binary search tree인 set을 이용해도 해결이 가능하다.)

 

 

segment tree의 value를 $\{ A_i,\ i\} $로 설정하여,

부모 node 마다 최솟값을 갱신해나가면 쉽게 쿼리를 처리해줄 수 있다.