(C++) - 백준(BOJ) 14428번 : 수열과 쿼리 16

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

14428번: 수열과 쿼리 16

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 n, q, a[100001];
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 query(int start, int end, int node, int left, int right){
    if(left > end || 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));
}

Node update(int start, int end, int node, int index, int y){
    if(index < start || index > end) return tree[node];
    if(start == end) return tree[node] = {y, index};
    int mid = (start + end) / 2;
    return tree[node] = min(
        update(start, mid, node * 2, index, y),
        update(mid + 1, end, node * 2 + 1, index, y)
    );
}

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

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