금광세그와 boj 16993
최근 ett/hld도 그렇고, 구간에 대해서 다루는 쿼리에 대해서 좀 깊게 공부해보고 있다. 일반적인 부분합 세그먼트 트리와는 다른 형태의 문제들을 해결해보고 있기에, 발상을 좀 정리해보고자 한다. 세그먼트 트리와 구간 세그먼트 트리의 주요 조건 및 세그트리가 주로 필요한 장소는 * 구간에 대한 쿼리를 진행하면서 * 각 쿼리당 처리시간이 빨라야 하고 * 인접한 두 구간이

바로 이전의 금광세그와 비슷한 구조체를 만들어 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;
    }
};

덧셈 연산자를 오버로딩해 두었으므로 일반적인 부분합 세그먼트 트리처럼 작성 및 사용하면 된다.

boj 24915 센터가 돋보여야 해