박성훈
바로 이전의 금광세그와 비슷한 구조체를 만들어 merge하는 유형의 세그트리를 연습해볼 수 있는 문제다.
L <= a < b < c <= R 일때
Ab-(Aa+Ac) 로 정의되는 무대의 매력의 최대치를 O(logN) 에 찾아내야 하는데,
이를 해결하기 위해서 세그트리를 도입해보도록 하겠다.
우선 이 문제를 보고 쉽게 착안할 수있는 것은
b는 크면 클수록 좋으며
a와 c는 작으면 작을수록 좋다는 것이다.
큰 숫자와 작은 숫자를 찾기 위해서 구조체 안에
- mx : [L,R] 에서의 최댓값
- mn : [L,R] 에서의 최솟값
을 각각 저장해주도록 하겠다. 이 부분까지는 평범한 최댓값/최솟값 세그와 같다.
이제 두 구간을 본격적으로 병합해 볼 것인데, 두 구간 A와 B에서 mx와 mn을 적절히 조합하면, (a,b) 쌍이나 (b,c) 쌍을 찾아낼 수 있다.
이들 각각을
- LtoM : [L,R] 구간에서 b-a의 값
LtoM = max({A.LtoM, B.LtoM, B.mx - A.mn}) - MtoR : [L,R] 구간에서 b-c의 값
MtoR = max({A.MtoR, B.MtoR, A.mx - B.mn})
으로 정의해줄 수 있다.
마침내 방금 구한 (a,b) 쌍의 오른쪽에 최솟값을 붙이고,
(b,c) 쌍의 왼쪽에 최솟값을 붙이는 것으로 정답을 구해줄 수 있다.
- ans : [L,R] 구간에서의 b-a-c 의 값
ans = max({A.ans, B.ans, A.LtoM - B.mn, B.MtoR - A.mn})
ans 에 담겨있는 값이 정답과도 같으므로, 이렇게 구간을 병합해 요구하는 정답을 구할 수 있게 되었고, 구간을 재빨리 병합할 수 있도록 segtree를 이용해서 AC를 받을 수 있다.
주의점
LtoM, MtoR, mx, ans의 초깃값은 -INF여야 하고, mn의 초깃값은 INF여야 한다.
segtree에서 query문 등을 작성할때 모든 변수가 0으로 초기화된 구조체를 반환할 시
정답이 정확히 계산되지 않을 수 있으므로 주의할 것.
또한 구간을 두번 병합해야 ans를 만들 수 있다는 특성상 [L,R] 구간의 크기가 3보다 작을 경우 정답이 존재하지 않으나, 지문 조건에 의해 이러한 경우가 입력으로 주어지지 않기 때문에 이 부분까지는 고려하지 않아도 된다.
정답 구조체 소스코드
struct st{
ll LtoM;
ll MtoR;
ll mn;
ll mx;
ll ans;
const st operator+(const st &K){
st R;
R.LtoM = max({LtoM, K.LtoM, K.mx - mn});
R.MtoR = max({MtoR, K.MtoR, mx - K.mn});
R.mx = max(mx, K.mx);
R.mn = min(mn, K.mn);
R.ans = max({ans, K.ans, K.MtoR-mn, LtoM-K.mn});
return R;
}
};덧셈 연산자를 오버로딩해 두었으므로 일반적인 부분합 세그먼트 트리처럼 작성 및 사용하면 된다.
