백준 17048번: 수열과 쿼리 24 (C++)

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

17408번: 수열과 쿼리 24

이번 문제는 각 구간 별로 최댓값 2개를 선별해내는 문제라고 생각하면 된다.

그러기 위해서 각 노드에 담겨있어야 하는 건 2개의 값으로 각 노드를 pair형으로 선언하기 때문에

트리 또한 pair형으로 선언하였다.

int arr[MAX];
pair<int, int> sgTree[MAX * 4];

 

트리를 init 하는 과정은 leaf node에 가면 한 노드에 2가지 값을 넣어야 하는데 배열 값 하나밖에 넣지 못한다.

이를 위해 pair 중 하나는 0을 넣어주었다.

>> INF 같은 엄청 큰 값은 안 된다. 트리를 구성하는 과정에 merge를 시키는데 큰 값을 순서로 뽑기 때문에 작은 값으로 할당한다.

void sgInit(int node, int start, int end){
    if(start == end){
        sgTree[node].first = 0;
        sgTree[node].second = arr[start];
        return;
    }
    
    int mid = (start + end) >> 1;
    sgInit(node * 2, start, mid);
    sgInit(node * 2 + 1, mid + 1, end);
    sgTree[node] = merge(sgTree[node * 2], sgTree[node * 2 + 1]);
}

업데이트 또한 init함수를 바탕으로 구현하였다.

>> 다만, second에 배열 값을 할당해두었기 때문에 leaf node에 갔을 때, second를 바꿔주는 것을 인지해야 한다.

void update(int start, int end, int node, int idx, int value){
    if(idx < start || end < idx) return;
    if(start == end){
        sgTree[node].second = value;
        return;
    }
    
    int mid = (start + end) >> 1;
    update(start, mid, node * 2, idx, value);
    update(mid + 1, end, node * 2 + 1, idx, value);
    sgTree[node] = merge(sgTree[node * 2], sgTree[node * 2 + 1]);
}

쿼리는 값 2개를 리턴 시키기 위해 pair형 함수로 구현하였다.

pair<int, int> query(int start, int end, int node, int left, int right){
    if(left > end || right < start){
        pair<int, int> none;
        none.first = 0;
        none.second = 0;
        return none;
    }
    if(left <= start && end <= right){
        return sgTree[node];
    }
    
    int mid = (start + end) >> 1;
    return merge(query(start, mid, node * 2, left, right),
            query(mid + 1, end, node * 2 + 1, left, right));
}

 

merge함수는 merge라 하기엔 애매하지만 global로 4 사이즈 크기에 배열을 선언해두고, pair변수 2개를 배열에 담아 정렬시켜서

값을 가져오도록 했다.

>> merge 안에서 배열을 선언하지 않은 이유는 혹시나 불필요한 메모리가 할당될까 봐 그랬다.

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    mergeV[0] = a.first;
    mergeV[1] = a.second;
    mergeV[2] = b.first;
    mergeV[3] = b.second;
    
    sort(mergeV.begin(), mergeV.end());
    
    a.first = mergeV[2];
    a.second = mergeV[3];
    return a;
}

 

[AC 코드]

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#define MAX (100000 + 1)
using namespace std;

int arr[MAX];
pair<int, int> sgTree[MAX * 4];
int n, m;
vector<int> mergeV(4);

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    mergeV[0] = a.first;
    mergeV[1] = a.second;
    mergeV[2] = b.first;
    mergeV[3] = b.second;
    
    sort(mergeV.begin(), mergeV.end());
    
    a.first = mergeV[2];
    a.second = mergeV[3];
    return a;
}

void sgInit(int node, int start, int end){
    if(start == end){
        sgTree[node].first = 0;
        sgTree[node].second = arr[start];
        return;
    }
    
    int mid = (start + end) >> 1;
    sgInit(node * 2, start, mid);
    sgInit(node * 2 + 1, mid + 1, end);
    sgTree[node] = merge(sgTree[node * 2], sgTree[node * 2 + 1]);
}

void update(int start, int end, int node, int idx, int value){
    if(idx < start || end < idx) return;
    if(start == end){
        sgTree[node].second = value;
        return;
    }
    
    int mid = (start + end) >> 1;
    update(start, mid, node * 2, idx, value);
    update(mid + 1, end, node * 2 + 1, idx, value);
    sgTree[node] = merge(sgTree[node * 2], sgTree[node * 2 + 1]);
}

pair<int, int> query(int start, int end, int node, int left, int right){
    if(left > end || right < start){
        pair<int, int> none;
        none.first = 0;
        none.second = 0;
        return none;
    }
    if(left <= start && end <= right){
        return sgTree[node];
    }
    
    int mid = (start + end) >> 1;
    return merge(query(start, mid, node * 2, left, right),
            query(mid + 1, end, node * 2 + 1, left, right));
}

int main(){;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    sgInit(1, 1, n);
    
    cin >> m;
    vector<pair<int, int>> result; // 디버깅 때문에 pair형 배열로 선언
    for(int i = 0; i < m; i++){
        int q, a, b;
        cin >> q >> a >> b;
        if(q == 1){
            update(1, n, 1, a, b);
        }
        else{
            pair<int, int> p = query(1, n, 1, a, b);
            result.push_back({p.first, p.second});
        }
    }
    
    for(int i = 0; i < result.size(); i++){
        //cout << result[i].first << ' ' << result[i].second << '\n';
        cout << result[i].first + result[i].second << '\n';
    }
    
    return 0;
}