수열과 최대 상승 쿼리 (백준 25639)

안녕하세요. 오늘은 최대상승 쿼리를 처리할 거예요.

문제

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

아이디어

세그트리로 풉시다.
tree[node]에는 node번지가 포함하는 구간에서 Ans,mx,mn이 있습니다. Ans는 그 구간에서의 최대 상승 값이고 mx는 최댓값, mn은 최솟값입니다. tree[node].Ans는 두 자식의 Ans값의 최댓값과 오른쪽 자식의 최댓값-왼쪽 자식의 최솟값중 최댓값이 됩니다. update도 똑같이 해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

struct Tree {
    ll Ans, mx, mn;
};

Tree tree[404040];
ll arr[101010];
Tree init(ll s, ll e, ll node)
{
    if (s == e)
        return tree[node] = { (ll)(0), arr[s], arr[s] };
    ll mid = (s + e) / 2;
    Tree first = init(s, mid, node * 2), second = init(mid + 1, e, node * 2 + 1);
    tree[node].Ans = max({ first.Ans, second.Ans, second.mx - first.mn });
    tree[node].mx = max(first.mx, second.mx);
    tree[node].mn = min(first.mn, second.mn);
    return tree[node];
}
Tree Query(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s)
        return { -1, (ll)(-2e9), (ll)(2e9) };
    if (l <= s && e <= r)
        return tree[node];
    ll mid = (s + e) / 2;
    Tree first = Query(s, mid, node * 2, l, r), second = Query(mid + 1, e, node * 2 + 1, l, r);

    Tree res;
    res.Ans = max({ first.Ans, second.Ans, second.mx - first.mn });
    res.mx = max(first.mx, second.mx);
    res.mn = min(first.mn, second.mn);
    return res;
}
void change(ll s, ll e, ll node, ll idx, ll val)
{
    if (idx < s || e < idx)
        return;
    if (s == e)
    {
        tree[node].Ans = 0;
        tree[node].mx = tree[node].mn = val;
        return;
    }

    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, val);
    change(mid + 1, e, node * 2 + 1, idx, val);
    tree[node].Ans = max({ tree[node * 2].Ans, tree[node * 2 + 1].Ans, tree[node * 2 + 1].mx - tree[node * 2].mn });
    tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
    return;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, Q, i, a, b, c;

    cin >> N;
    for (i = 1; i <= N; i++)
        cin >> arr[i];
    init(1, N, 1);

    cin >> Q;
    for (i = 0; i < Q; i++)
    {
        cin >> a >> b >> c;
        if (a == 1)
            change(1, N, 1, b, c);
        else
            cout << Query(1, N, 1, b, c).Ans << "\n";
    }
}

감사합니다.