[BOJ] 17408 수열과 쿼리 24

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

17408번: 수열과 쿼리 24

알고리즘: Segment tree

 

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

---

접근:

$l\le i < j \le r$ 구간에서 $A_i+A_j$의 최댓값을 구하는 문제이다.

 

$A_i+A_j$가 최대가 되려면 $A_i$와 $A_j$가 각각 구간 내에서 최댓값, 두번째 최댓값이 되야한다.

 

따라서 [l, r] 구간에서 최댓값을 구하는 segment tree를 약간 변형시켜서,

노드에다가 최댓값과 두번째 최댓값을 저장하는 방식으로 해결하였다. 

 

---

다른 사람들 풀이를 보니, 알아두면 괜찮은 기법이 있었다.

{최댓값, 두번째 최댓값}을 저장하는게 아니라, {최댓값, 최댓값의 index}를 저장하는거다.

[l, r] 쿼리를 통해 최댓값을 찾고 -> [l, i-1], [i+1, r] 쿼리를 통해 두번째 최댓값을 찾는다.

 

이 기법은 나중에 한번쯤 다른 문제에 사용할 것 같다.