[백준 14427] 수열과 쿼리 15 (Gold II)

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

14427번: 수열과 쿼리 15

 

세그먼트 트리 풀이가 정해라고 알려져 있다. 이 글에서는 Tree set 풀이를 다룬다. Tree set 풀이는 Red-black Tree로 구현한 set/map 자료구조가 O(log n) 속도로 최솟값 또는 최댓값을 찾아줄 수 있다는 성질을 이용한다. Red-black Tree는 max height O(log n)을 보장하기는 하지만 세그먼트 트리가 포화 이진 트리의 모습을 보여주는데 반해 RB Tree는 그런 게 없다. 그래서 속도는 2~3배 느림. 대신 구현이 쉽다.

 

먼저 array로 수열 전체를 관리한다. 수열이 업데이트될 때마다 array도 업데이트해가면, 수열의 인덱스만으로 그 위치의 값을 O(1)에 구할 수 있다는 것을 보장할 수 있다. 그리고 std::set<std::pair<int, int>>를 하나 만든다. pair은 first에 value, second에 index를 들고 있는다. 이렇게 하면, std::set 내부의 원소들이 first = value -> second = index 순으로 정렬되기 때문에, 우리가 원하는 것과 정확히 일치한다. 마지막으로 set.first() 메소드로 최솟값을 찾아준다.

 

#include <bits/stdc++.h>

void solve() {
    int n; std::cin >> n;
    
    std::vector<int> input(n);
    std::set<std::pair<int, int>> set;
    
    for (int i = 0; i < n; ++i) {
        std::cin >> input[i];
        set.emplace(input[i], i);
    }
    
    int q; std::cin >> q;
    
    for (int i = 0; i < q; ++i) {
        int qnum; std::cin >> qnum;
        if (qnum == 2) {
            std::cout << set.begin()->second + 1 << '\n';
        } else {
            int idx, v; std::cin >> idx >> v; --idx;
            int value_of_idx = input[idx];
            set.erase(set.find(std::make_pair(value_of_idx, idx)));
            set.emplace(v, idx);
            input[idx] = v;
        }
    }
}