[백준 14428] 수열과 쿼리 16

 

 최근에 프로그래머스 문제들을 몰아서 푸느라 백준에서는 매일 간단한 문제만 하나씩 풀었는데, 오랜만에 좋은 문제를 만났다.

 문제를 읽으면 바로 느껴지겠지만 세그먼트 트리 문제다. 다른 부분은 일반적인 세그먼트 트리를 이용한 문제와 다를 바가 없지만, 주의해야 하는 부분은 쿼리의 결과로 최솟값이 위치한 인덱스를 출력해야 한다는 것이다.

 따라서 세그먼트 트리에 값으로 최솟값만 저장할 게 아니라 최솟값이 위치한 인덱스를 함께 저장하는 방법으로 접근했다. 그리고 문제 조건에서 최솟값이 구간 내에 여러 개 있을 경우 가장 작은 인덱스를 출력하도록 되어있으므로, C++ 기준 pair를 이용하되 {최솟값, 인덱스} 순서로 배치해서 비교 연산을 수월하게 했다.

 

 위 내용을 토대로 세그먼트 트리를 초기화, 업데이트, 쿼리하는 함수를 구현하면 끝이다. 예전에 풀었던 구간 곱 문제와 상당히 유사하니 이를 참고해 보면 좋을 것 같다.

https://winterry.tistory.com/140

[백준 11505] 구간 곱 구하기

 

 

#include <iostream>
#include <vector>
#define INF 1000000001

using namespace std;

vector<int> arr;
vector<pair<int, int> > segTree;

pair<int, int> initTree(int l, int r, int ind) {
    if(l==r) {
        return segTree[ind] = {arr[l], l};
    } else {
        int mid = (l+r)/2;
        auto leftSeg = initTree(l, mid, ind*2);
        auto rightSeg = initTree(mid+1, r, ind*2+1);

        if(leftSeg<rightSeg) {
            return segTree[ind] = leftSeg;
        } else {
            return segTree[ind] = rightSeg;
        }
    }
}

pair<int, int> query(int l, int r, int ind, int lBound, int rBound) {
    if(r<lBound || l>rBound) {
        return {INF, -1};
    } else if(l>=lBound && r<=rBound) {
        return segTree[ind];
    } else {
        int mid = (l+r)/2;
        auto leftSeg = query(l, mid, ind*2, lBound, rBound);
        auto rightSeg = query(mid+1, r, ind*2+1, lBound, rBound);

        if(leftSeg<rightSeg) {
            return leftSeg;
        } else {
            return rightSeg;
        }
    }
}

pair<int, int> update(int l, int r, int ind, int targetInd, int newNum) {
    if(targetInd<l || targetInd>r) {
        return segTree[ind];
    } else if(l==r) {
        return segTree[ind] = {newNum, targetInd};
    } else {
        int mid = (l+r)/2;
        auto leftSeg = update(l, mid, ind*2, targetInd, newNum);
        auto rightSeg = update(mid+1, r, ind*2+1, targetInd, newNum);

        if(leftSeg<rightSeg) {
            return segTree[ind] = leftSeg;
        } else {
            return segTree[ind] = rightSeg;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n;
    arr = vector<int>(n+1);
    segTree = vector<pair<int, int> >(n*4);    

    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }

    initTree(1, n, 1);

    cin >> m;

    int cmd, i, j;
    while(m--) {
        cin >> cmd >> i >> j;
        if(cmd==1) {
            update(1, n, 1, i, j);
        } else {
            cout << query(1, n, 1, i, j).second << "\n";
        }
    }
}