[백준 25639번] 수열과 최대 상승 쿼리

---

25639번: 수열과 최대 상승 쿼리

---

 

목차

• 사전 지식
• 문제 접근
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 특히, 세그먼트 트리가 쿼리를 처리하는 과정을 이해하고 있어야 한다.

 

 

 

문제 접근

문제에서 길이가 $N$인 배열($\small{a_1, a_2, \cdots, a_N}$)과 $Q$개의 쿼리(query)가 주어진다.

이 배열에서 아래의 두 개의 query만 잘 수행하면 문제를 풀 수 있다.

1. 1 k x: $a_k$를 $x$로 바꾼다.
2. 2 l r: 구간 $\small{[l, r]}$의 최대 상승 값을 출력한다. (최대 상승 값의 정의는 문제를 참조하기 바란다)

 

query1 처리

query1은 배열에서 원소를 바꾸는 작업으로 arr[k] = x를 수행하면 된다.

 

query2 처리

query2을 처리하는 방법은 query1에 비해 매우 까다롭다.

 

[기초적인 방법]

기본적인 방법으로 $l, r$에 대해 $l \leq i \leq j \leq r$를 만족하는 모든 $(i, j)$의 조합을 살펴보면 구할 수 있다.

하지만, $(i, j) \ $경우의 수가 약 $_{l-r+1} \mathrm{C}_{2} \ $개 이므로 쿼리 한 번당 최대 $O(N^2)$이 걸린다.

쿼리의 개수가 $Q$개 이므로, 전체 시간 복잡도는 최악의 경우에 $O(Q \cdot N^2)$이 나온다.
따라서, 이러한 방법으로 처리하는 것은 TLE(Time Limit Exceede) 오류가 나게 된다.

 

[조금 더 효율적으로]

조금 더 생각해보면 더 효율적인 방법을 떠올릴 수 있다.

인덱스 $j$를 고정한다고 하면, $max(a_j - a_i)$를 어떻게 구할 수 있을까?
$l \leq i \leq j$에서 값이 가장 작은 $a_i$를 구하면 $max(a_j - a_i)$를 구할 수 있다.

 

즉, $l \leq j \leq r$에서 모든 $j$에 대해 $max(a_j - a_i)$의 값을 살펴보면 쿼리의 답을 구할 수 있다.

이를 구현하는 법은, 지금까지 탐색한 가장 작은 원소를 저장하며 구간 $[l, r]$을 한 번 탐색하면 된다.

int query2(int l, int r) {
   int ret = 0;
   int mn = int(1e9); // 현재 살펴본 원소 중 최소값

   for (int j=l; j<=r; j++) {
      mn = min(mn, arr[j]);
      ret = max(ret, arr[j]-mn);
   }

   return ret;
}

 

하지만, 이러한 방법을 쓴다고 해도 쿼리 한 번을 처리하는 데 최대 $O(N)$이 걸린다.

즉, 전체 시간 복잡도는 $O(Q \cdot N)$으로 여전히 TLE 오류가 나게 된다. 😭

 

여기서 알 수 있는 점은 $Q \leq 100,000 \ $이므로 query2를 $O(\log N)$ 정도에 (가깝게) 처리해야 한다.

즉, query2에서 구간 $[l, r]$을 처리할 때 일일이 살펴보는 것이 아닌 합쳐서 살펴봐야 한다는 것이다!

 

 

 

문제 풀이

query2에서 구간 $[l, r]$을 처리할 때 구간을 어떻게 합쳐서 살펴볼 수 있을까?

구간을 살펴본다고 하면 떠오르는 자료구조는 세그먼트 트리(Segment Tree)일 것이다.

하지만, 이를 사용하기 전에 먼저 알아야 할 중요한 사실이 있다.

중요한 사실

구간 $\small{[a, b]}$의 최대 상승 값과 구간 $\small{[b+1, c]}$의 최대 상승 값을 알고 있으면 구간 $\small{[a, c]}$의 최대 상승 값을 알 수 있을까? (단, $\small{a \leq b \leq c})$

답은 Yes이며, 어떻게 구할 수 있는지 이제 설명하겠다.
구간이 합쳐져도 구간 $\small{[a, b]}$에서 나오는 최대 상승 값과 구간 $\small{[b+1, c]}$에서 나오는 최대 상승값은 유효하다.
그리고, 추가적으로 살펴보아야 하는 것은 구간이 합쳐지면서 생기는 최대 상승 값이다.
이를 구하는 방법은 구간 $\small{[b+1, c]}$의 최대값에서 $\small{[a, b]}$의 최소값을 빼면 구할 수 있다.

 

즉, 정리하면 다음 중에서 최대값을 고르면 된다.

• $\small{[a, b]}$에서 나오는 최대 상승 값
• $\small{[b+1, c]}$에서 나오는 최대 상승값
• $\small{[b+1, c]}$의 최대값에서 $\small{[a, b]}$의 최소값을 뺀 값

 

문제 풀이

이제 위의 중요한 사실을 이용하여 세그먼트 트리를 구성해보자.

두 구간을 통해서 합친 구간의 최대 상승값을 구할 때 필요한 값은 구간에서의 최소값, 최대값, 최대 상승 값이다.

따라서, 세그 먼트 트리의 각 노드는 (구간의 최소값, 구간의 최대값, 구간의 최대 상승 값) 정보를 담고 있어야 한다.

각 노드에 3개의 정보를 저장해야 하기 때문에 구조체를 쓰면 된다.

 

리프 노드의 인덱스는 문제에서 주어진 배열의 인덱스와 대응하며

리프 노드에 대응하는 배열에 들어 있는 원소의 값을 $x$라고 할 때, 리프 노드의 초기값은 ($x$, $x$ ,$0$)이다.

(세그먼트 트리를 업데이트하는 update()는 간단하지만, query2를 처리하는 query()의 경우 조금 까다로우니 주의하자)