(C++) - 백준(BOJ) 14427번 : 수열과 쿼리 15

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

14427번: 수열과 쿼리 15

segment tree로 푼 문제였습니다.

 

 

 

📕 풀이방법

📔 입력 및 초기화

 가장 작은 값, 그 중에서 가장 작은 인덱스를 뽑아야 하기 때문에 struct Node를 선언해 바로 index를 뽑을 수 있도록 변수들을 선언했습니다. 또한 min함수를 struct에 대해 사용하기 위해 연산자 오버로딩(함수 중복정의) 을 사용했습니다.

 수를 입력 받고 각 구간의 가장 작은 값 그리고 해당하는 인덱스를 tree라는 vector형 변수에 저장합니다.

 

 

📔 풀이과정

 1. op가 1이라면 a,b라는 int형 변수를 입력하고 update해줍니다.

 

 2. op가 2라면 해당하는 구간의 값들과 인덱스들을 확인해 해당하는 struct를 반환해줍니다.

 

📔 정답출력

 배열이 0 ~ n -1까지이므로 뽑아낸 struct에서 인덱스 + 1을 출력합니다.

---

 

 

📕 Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct Node { int num = INF, idx = INF; };
int nums[100001], n, k, q;
vector <Node> tree(400001);

bool operator < (const Node &a, const Node &b){
    if(a.num == b.num) return a.idx < b.idx;
    return a.num < b.num;
}

Node init(int start, int end, int node){
    if(start == end) return tree[node] = {nums[start], start};
    int mid = (start + end) / 2;
    return tree[node] = min(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}


Node update(int start, int end, int node, int index, int num){
    if(index < start || end < index) return tree[node];
    if(start == end) return tree[node] = {num, index}; 

    int mid = (start + end) / 2;

    return tree[node] = min(
        update(start, mid, node * 2, index, num),
        update(mid + 1, end, node * 2 + 1, index, num)
    );
}

Node query(int start, int end, int node, int left, int right){
    if(end < left || start > right) return {INF, INF};
    if(left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;

    return min(
        query(start, mid, node * 2, left, right),
        query(mid + 1, end, node * 2 + 1, left, right)
    );
}

int main(){
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> nums[i];
    cin >> q;
    init(0,n-1,1);
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int a, b;
            cin >> a >> b;
            update(0,n-1,1,a-1,b);
        }
        else{
            Node ans = query(0,n-1,1,0,n-1);
            cout << ans.idx + 1 << '\n';
        }
    }

}