[백준 17408] 수열과 쿼리 24

문제

www.acmicpc.net/problem/17408

 

알고리즘

segment tree

 

풀이

점 갱신과 구간 사이의 두 값의 합의 최댓값을 묻는 문제입니다. 

 

두 번째 쿼리는 세그먼트 트리에 최댓값을 저장하면서도 추가적으로 최댓값의 인덱스를 저장한다면 해결가능합니다. 주어진 범위가 $l, r$일 때, $query(l,r)$을 사용해서 최댓값 $M$과 인덱스 $idx$를 얻었다면 $query(l,idx-1)$와 $query(idx+1,r)$을 사용해 두 번째로 큰 값을 구하면 됩니다. 코드를 간결하게 하려고 $cmp$함수를 작성해 사용했습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef pair<int, int> pii;
#define left (i << 1)
#define right (i << 1 | 1)

int N, Q;
pii tree[200005];

pii cmp(pii a, pii b) {
    if (a.first > b.first)
        return a;
    return b;
}

void update(int i, int val) {
    i += N;
    tree[i].first = val;
    for (i >>= 1; i; i >>= 1) {
        tree[i] = cmp(tree[left], tree[right]);
    }
}

pii query(int l, int r) {
    pii ret = { 0, 0 };
    l += N;
    r += N;
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) {
            ret = cmp(ret, tree[l++]);
        }
        if (!(r & 1)) {
            ret = cmp(ret, tree[r--]);
        }
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        cin >> tree[i + N].first;
        tree[i + N].second = i;
    }
    for (int i = N - 1; i; --i) {
        auto& [f, s] = tree[i];
        tree[i] = cmp(tree[left], tree[right]);
    }

    cin >> Q;
    while (Q--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            update(b - 1, c);
        } else {
            auto [d, e] = query(b - 1, c - 1);
            cout << max(query(b - 1, e - 1).first, query(e + 1, c - 1).first) + d << '\n';
        }
    }
    return 0;
}