백준 17408번: 수열과 쿼리 24 (플래티넘 IV)

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

17408번: 수열과 쿼리 24

수열이 쭉~ 주어지고, 이 수열의 요소들이 항상 변할 수 있는 상황일 때,
l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서 최댓값을 출력하라고 한다.

 

이게 뭔

"l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서 최댓값"이라고 써놓으니 전혀 와닿지가 않는다.
쉽게 해석하면 구간 l~r에서 두 요소를 합한 게 최대가 되게 하라는 것이다.

 

이건 또 뭔

이것도 어렵다고?
더 쉽게 문제를 해석하면, 구간 l~r의 젤 큰 요소와 두번째로 큰 요소를 더하면 된다.

---

구간의 최댓값을 구하는 세그먼트 트리는 이미 어느정도 연습해서 쉽게 만들 수 있을 것 같다.
그러면 구간의 두번째로 큰 요소는 어떻게 구할까?

별거 없다. 그냥 최댓값을 저장하는 세그먼트 트리에 두번째로 큰 값도 같이 저장해놓으면 된다.
세그먼트 트리의 각 노드는 2개의 값을 저장하게 된다.

트리의 상위 노드에서는 하위 노드에서 가져온 총 4개의 값 중, 큰 2개를 뽑아 저장한다.
구현 방법은 여러가지가 있겠지만, 본인은 리스트에 넣고 정렬하는 방식을 썼다.

// 수열과 쿼리 24
// 세그먼트 트리

// l-r 구간 내에서 최댓값 2개를 찾는 문제이므로
// 트리가 가장 큰 2개의 값을 저장하면 됨

#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

typedef long long ll;

int N, M, a;
std::vector<std::pair<ll, ll> > segTree;

std::pair<ll, ll> updateTree(int node, int s, int e, int ind, int val){
    if(ind < s || e < ind){
        return segTree[node];
    } else {
        if(s == e){
            segTree[node].first = val;
            segTree[node].second = 0;
            return segTree[node];
        } else {
            int mid = (s+e)/2;
            std::pair<ll, ll> left = updateTree(node*2, s, mid, ind, val);
            std::pair<ll, ll> right = updateTree(node*2+1, mid+1, e, ind, val);
            ll arr[4] = {left.first, left.second, right.first, right.second};
            std::sort(arr, arr+4, std::greater<ll>());
            segTree[node].first = arr[0];
            segTree[node].second = arr[1];
            return segTree[node];
        }
    }
}
std::pair<ll, ll> query(int node, int s, int e, int l, int r){
    if(r < s || e < l){
        return std::make_pair(0, 0);
    } else {
        if(l <= s && e <= r){
            return segTree[node];
        } else {
            int mid = (s+e)/2;
            std::pair<ll, ll> left = query(node*2, s, mid, l, r);
            std::pair<ll, ll> right = query(node*2+1, mid+1, e, l, r);
            ll arr[4] = {left.first, left.second, right.first, right.second};
            std::sort(arr, arr+4, std::greater<ll>());
            return std::make_pair(arr[0], arr[1]);
        }
    }
}

int main(){

    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> N;

    int height = (int)std::ceil(log2(N));
    int size = (1 << (height + 1));
    segTree.resize(size);

    for(int i = 1; i <= N; i++){
        std::cin >> a;
        updateTree(1, 1, N, i, a);
    }

    std::cin >> M;

    for(int i = 0; i < M; i++){
        int l, r;
        std::cin >> a >> l >> r;

        if(a == 1){
            updateTree(1, 1, N, l, r);
        } else {
            std::pair<ll, ll> res = query(1, 1, N, l, r);
            std::cout << res.first + res.second << '\n';
        }
    }

    return 0;
}