풀이
type = 2인 query에 대해 l, r 이 주어지면 l ~ r 범위의 node에 대해 A(i) + A(j)의 결과가 최댓값인 경우를 출력하면 된다.
i, j은 문제에서 주어진 l <= i < j <= r이 전부이기 때문에, l ~ r 구간에 대해 가장 큰 값과, 두번째로 큰 값을 찾아서 더해주면 된다.
node에 { 가장 큰 값, 두번째로 큰 값 } pair을 저장해주고, init, update, query 과정에서 pair을 새롭게 구해주는 함수를 이용하면 된다.
단, { 가장 큰 값, 두번째로 큰 값 }이 어떻게 존재할 지 모르기 때문에 두 node가 가지는 pair의 모든 쌍에 대해 비교가 필요하다.
결국은 주어진 구간에 대해 { 가장 큰 값, 두번째로 큰 값 } 이 정답임을 알 수 있기에,
개인적으로 체감 난이도는 그렇게 높지 않았던 문제이다. (플래5~4 정도)
10868번: 최솟값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는
www.acmicpc.net
위 문제에서 최솟값이 아닌 최댓값을 구하는 문제로 바꾸고, node에 하나의 값이 아닌 { 가장 큰 값, 두번째로 큰 값 }라는 쌍을 넣어주면 풀린다고 볼 수 있다.
단, 위에서 언급했듯 쌍의 요소에 대해 전부 비교해주어야 한다.
소스코드
출처
17408번: 수열과 쿼리 24
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 26566] Pizza [Python] (0) | 2023.05.28 |
|---|---|
| [백준 26592] Triangle Height [Python] (0) | 2023.05.27 |
| [백준 28074] 모비스 [Python] (0) | 2023.05.25 |
| [백준 28097] 모범생 포닉스 [Python] (0) | 2023.05.23 |
| [백준 21354] Äpplen och päron [Python] (0) | 2023.05.21 |