PS 일기 2024년 3월 6일 (4일 차) (13557번 수열과 쿼리 10)

PS 일기 2024년 2월 8일 (3일 차)

PS 일기란?

PS 실력 향상을 목적으로 날마다 푼 문제를 회고하는 것입니다. 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지 등을 기록합니다.

오늘의 문제

13557번 수열과 쿼리 10

알고리즘 분류

• Segment Tree
• 누적합

문제 풀이

$P_i = A_i + P_{i-1} (1 \leq i \leq N)$

을 누적합이라 할 때

$\sum_{k = s}^{e} A_k = P_e - P_{s-1}$

입니다. $P_e - P_{s-1}$를 최대화하기 위해선 $P_e$가 가장 큰 값, $P_{s-1}$가 가장 작은 값 이어야 합니다. 이를 식으로 표현하면 이와 같습니다.

$\max_{k = x2}^{y2}P_k - \min_{k = x1-1}^{y1-1}P_k$

s값은 -1 한 상태의 min값을 구해야 하기 때문에 $[x1-1, y1-1]$구간에서 min값을 구해야 합니다. 그래서 세그먼트 트리로 min 값과 max값을 관리하면 $(x1, y1)$와 $(x2, y2)$가 겹치지 않은 경우를 계산할 수 있습니다.

만약 $(x1, y1)$과 $(x2, y2)$가 겹친다면($x2 \leq y1$라면) 3가지의 case로 나누어 답을 계산할 수 있습니다.

1. $x1 \leq s \leq y1 \leq e \leq y2$ 인 경우 $[x1, y1]$구간에서 min값을 구하고 $[y1, y2]$구간에서 max값을 구해 답을 구합니다.
2. $x1 \leq s \leq x2 \leq e \leq y2$ 인 경우 1. 의 경우와 비슷하게 $[x1, x2]$구간에서 min값을 구하고 $[x2, y2]$구간에서 max값을 구해 답을 구합니다.
3. $x2 \leq s \leq e \leq y1$ 인 경우 세그먼트 트리에서 두 자식 노드를 합칠 때 (merge 함수) 왼쪽 자식의 min 값과 오른쪽 자식의 max 값의 차이, 왼쪽 자식의 max diff와 오른쪽 자식의 max diff 중 가장 큰 값을 선택합니다.

구현

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MAXN = 100005;
const ll INF = 1e18;

struct T {
    ll mn, mx;
    ll mx_diff;
};

ll N, M, arr[MAXN], psum[MAXN];
T tree[4*MAXN];

T merge(T l, T r)
{
    T ret;
    ret.mn = min(l.mn, r.mn);
    ret.mx = max(l.mx, r.mx);
    ret.mx_diff = max({l.mx_diff, r.mx_diff, r.mx - l.mn});
    return ret;
}

void init(ll s = 0, ll e = N, ll idx = 1)
{
    if(s == e) {
        tree[idx].mn = tree[idx].mx = psum[s];
        tree[idx].mx_diff = -INF;
        return;
    }
    ll m = (s + e) >> 1;
    init(s, m, 2*idx); init(m+1, e, 2*idx+1);
    tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
}

T query(ll l, ll r, ll s = 0, ll e = N, ll idx = 1)
{
    if(e < l || r < s) return T{INF, -INF, -INF};
    if(l <= s && e <= r) return tree[idx];
    ll m = (s + e) >> 1;
    return merge(query(l, r, s, m, 2*idx), query(l, r, m+1, e, 2*idx+1));
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N;
    for(ll i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    for(ll i = 1; i <= N; i++) {
        psum[i] = arr[i] + psum[i-1];
    }
    init();
    cin >> M;
    for(ll i = 0; i < M; i++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ll ans = -INF;
        if(x2 <= y1) {
            T t = query(x2 - 1, y1);
            ans = max(ans, t.mx_diff);

            T l = query(x1 - 1, y1 - 1);
            T r = query(y1, y2);
            ans = max(ans, r.mx - l.mn);

            l = query(x1 - 1, x2 - 1);
            r = query(x2, y2);
            ans = max(ans, r.mx - l.mn);
        } else {
            T l = query(x1 - 1, y1 - 1);
            T r = query(x2, y2);
            ans = max(r.mx - l.mn, ans);
        }
        cout << ans << "\n";
    }
}

후기

이 글을 보는 사람이 있을까?