https://jungol.co.kr/problem/8356
| 시간 제한 | 메모리 제한 |
| 2초 | 512MB |
문제
위 그림처럼 N 잔의 콜라들과 N 개의 피자 조각들이 일렬로 나열되어 있다.
각 콜라들과 피자 조각들은 맛의 정도가 다 다른데, 이는 정수로 주어진다.
정올이는 이 중 1 잔의 콜라와, 1 개의 피자 조각을 선택하여 먹는다.
항상 콜라는 왼손으로, 피자는 오른손으로 먹기에,
선택된 피자 조각의 위치는 선택된 콜라의 위치보다 오른쪽에 있어야 한다. ( 인덱스가 더 커야 한다. )
이 조건을 만족하면서 콜라와 피자 조각을 골랐을 때, 둘의 맛의 합이 최대가 되도록 하고 싶다.
Q 개의 명령이 들어오는데, 세 가지 형태 중 하나로 들어온다.
- i 번째 콜라의 맛을 x 로 바꾼다.
- i 번째 피자 조각의 맛을 x 로 바꾼다.
- 두 수 L, R ( 1 ≤ L < R ≤ N ) 에 대하여, L번째 ~ R번째 칸 범위에서만 콜라와 피자 조각을 고를 수 있을 때, 맛의 합의 최대를 출력한다.
입력
첫 줄에 N 이 입력된다. ( 1 ≤ N ≤ 100,000 )
두 번째 줄에, 일렬로 콜라들의 맛이 N 개의 정수로 입력된다. ( 100만 이하의 자연수 )
세 번째 줄에, 일렬로 피자 조각들의 맛이 N 개의 정수로 입력된다. ( 100만 이하의 자연수 )
네 번째 줄에 쿼리의 수 Q 가 입력된다. ( 1 ≤ Q ≤ 100,000 )
세 가지 형태의 명령들이 입력된다.
- 1 i x : i 번째 콜라의 맛을 x 로 바꾸는 명령 ( 1 ≤ i ≤ N, x 는 100만 이하의 자연수 )
- 2 i x : i 번째 피자 조각의 맛을 x 로 바꾸는 명령 ( 1 ≤ i ≤ N, x 는 100만 이하의 자연수 )
- 3 L R : L번째 ~ R번째 칸 범위에서만 콜라와 피자 조각을 고를 수 있을 때, 맛의 합의 최대를 출력하는 명령
출력
3번 명령이 들어올 때마다 적절한 답을 출력하자. 무조건 3번 명령은 1번 이상 주어진다.
풀이
어떤 위치 $i$에서 콜라를 골랐다면 콜라는 $i$로부터 왼쪽으로, 피자는 $i+1$로부터 오른쪽으로 최대 값을 얻어야 합니다. 그런데 쿼리가 10만회, `N`도 최대 10만이라 $O(N^2)$으로는 시간 제한이 터집니다.
어떤 구간 $[L, R]$을 반으로 나눠서 `left`와 `right`로 관리한다면 콜라와 피자를 고르는 방법은 반드시 다음 셋 중 하나입니다.
- 콜라와 피자를 모두 `left`구간에서 고른다.
- 콜라와 피자를 모두 `right`구간에서 고른다.
- 콜라는 `left`에서, 피자는 `right`에서 고른다.
세 개의 세그먼트 트리를 만듭시다. `node` 구간에서 선택할 수 있는 최선의 콜라를 `cola[node]`, 피자를 `pizza[node]`라고 합시다. 그리고 `node` 구간에서 규칙에 따라 최선의 콜라와 피자를 선택할 수 있는 방법을 `total[node]`라고 하겠습니다. 그럼 어떤 구간 `x`에 대해 하위 구간을 `x*2`와 `x*2+1`로 나눌 수 있습니다. 각각 구간 `x`의 왼쪽과 오른쪽을 담당합니다. 그럼 구간 `x`에 대한 세 가지 값은 이렇게 정리할 수 있습니다.
left = x*2
right = x*2+1
cola[x] = max(cola[left], cola[right])
pizza[x] = max(pizza[left], pizza[right])
total[x] = max(total[left], total[right], cola[left]+pizza[right])
$i$번째 콜라 또는 피자의 맛을 $x$로 바꾸는 명령은 리프로부터 루트로 갱신해나가며 $O(logN)$으로 실행할 수 있습니다.
$[L, R]$ 구간의 최적해 역시 구간을 덮는 `node`만 찾아 순차적으로 `기존의 최적해`와 `기존의 최대 콜라`, `새로운 구간의 최대 피자`, `새로운 구간의 최적해`로 나눠 찾을 수 있습니다.
정답 코드
# 생략
