문제의 첫 줄을 읽자마자, 'a번째 정수부터 b번째 정수까지' 이 문구가 눈에 들어왔다. 이 말인 즉슨, 세그먼트 트리를 이용할 가능성이 매우 높다는 뜻. 그리고 뒤에를 읽었더니 최솟값과 최댓값을 구하라는 얘기가 보인다. 그리고 입력되는 수의 범위를 봤더니 N과 M이 모두 10^5 이하의 자연수라는 조건이 보였다. 즉, 만약 시간복잡도가 O(N)인 알고리즘을 써야한다면, 10^10번의 계산을 해야한단 의미였다. 이는 2초라는 시간 내에 절대적으로 불가하므로 처음 생각했던 세그먼트 트리의 개념을 이용해서 문제를 풀기로 했다. 그런데 약간의 고민이 생겼다. 최대와 최소 모두를 출력해야 하는데 어떻게 세그먼트 트리로 나타내지? 그래서 2개의 세그먼트 트리를 이용해 각각 특정 구간에서의 최대와 최소를 나타내는..
