[BOJ] 13557 수열과 쿼리 10

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

13557번: 수열과 쿼리 10

알고리즘: Segment tree

 

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

---

$A_i+...+A_j$의 최댓값을 구하는 것은 DP로 $O(N)$만에 해결이 가능하다.

다만 이 문제에선 주어지는 구간마다 최댓값을 구해줘야 한다.

 

쿼리 개수가 많으므로 $O(N)$이 아니라 그보다 더 빠른 시간안에 해결해야 한다.

따라서 segment tree를 이용하여 $O(logN)$만에 구하는 방법을 생각해보았다.

 

기본적인 아이디어는 분할정복을 이용하는 것이다.

두 구간을 합쳤을 때, 부분 수열의 최댓값이 가능한 경우는 아래 그림과 같다.

lmax: 제일 왼쪽의 원소를 포함했을 때 최대

rmax: 제일 오른쪽의 원소를 포함했을 때 최대

sum : 구간을 모두 더한 거

두 구간을 합친다고 하면,

new lmax = max(1번, 2번)

new rmax = max(4번, 5번)

new sum = 6번

이렇게 될 것이고, 최댓값은 new lmax, new rmax, 3번 중 하나가 될 것이다.

(6번이 최대일 시, new lmax = new rmax = new sum 이기에 신경 쓸 필요가 없다.) 

 

다만 문제에서 요구하는 부분 수열은 [l, r]의 구간에서 부분 수열의 양 끝을 선택하는게 아니라,

[x1, y1]과 [x2, y2] 같이 두 구간에서 각각 수열의 양 끝을 선택하는거라 구현이 좀 복잡해진다...

 

 

[x1, y1]과 [x2, y2]는 위 그림과 같이 두 가지의 경우의 수가 존재한다.

1은 서로 겹치는 구간이 없는거고 2는 서로 겹치는 구간이 존재하는 경우이다.

 

1번 같은 경우는 답을 구하기가 쉽다.

아래 그림과 같이 가운데 구간 (y1, x2)는 무조건 부분 수열에 포함된다는 사실만 발견하면 된다.

 

2번이 조금 까다롭고 구현도 빡셌다..

우선 구간을 아래 그림과 같이 세 구간으로 나눠줄 수 있다.

[x1, x2), [x2, y1], (y1, y2]

 

그럼 최댓값이 가능한 경우의 수는 아래 그림과 같이 네 가지 경우가 있다.

 

이를 잘 구현하면 AC... 구현하는게 너무 힘들었던 문제