[14428] 수열과 쿼리 16

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

14428번: 수열과 쿼리 16

<문제>
최소값을 찾는 세그먼트 트리를 구현하고, 값 대신 인덱스를 리턴하도록 만들면 된다.
리프노드에는 인덱스가, 그 외에는 구간중 최소값을 갖는 인덱스가 들어가도록 구성한 다음에,
인덱스를 리턴하는 부분을 처리하기 위해 minIdx라는 함수를 만들었다.
단순히 최소값을 리턴하는 문제라면, (left>end || right<start)일때 INF를 리턴하면 되지만
이 문제는 -1같이 절대 인덱스로는 불가능한 숫자를 리턴하고, 이를 아예 판단에서 배제하는 과정이 필요했다.
query에서 범위가 대상 밖일때에는 -1을 리턴하고, minIdx에서 한쪽이 -1인 경우는 반대쪽을
리턴하도록 함으로써 인덱스에 대한 처리가 끝난다.

<소스코드>

#include<stdio.h>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
typedef long long ll;
vector <ll>num;
vector <ll>segTree;
int n, m;
ll minIdx(ll x, ll y) {
    if (x == -1)return y;
    if (y == -1)return x;
    if (num[x] == num[y])return x < y ? x : y;
    return num[x] < num[y] ? x : y;
}
ll makeSegTree(int node, int start, int end) {
    if (start == end)return segTree[node] = start;
    int mid = (start + end) / 2;
    return segTree[node] = minIdx(makeSegTree(node * 2, start, mid), makeSegTree(node * 2 + 1, mid + 1, end));
}
ll updateSegTree(int node, int start, int end, int idx) {
    if (idx<start || idx>end)return segTree[node];
    if (start == end) {
        return segTree[node];
    }
    int mid = (start + end) / 2;
    return segTree[node] = minIdx(updateSegTree(node * 2, start, mid, idx),
        updateSegTree(node * 2 + 1, mid + 1, end, idx));
}
ll query(int node, int start, int end, int left, int right) {
    if (left > end || right < start)return -1;
    if (left <= start && end <= right)return segTree[node];
    int mid = (start + end) / 2;
    return minIdx(query(node * 2, start, mid, left, right), query(node * 2 + 1, mid + 1, end, left, right));
}
int main(void) {
    int i;
    scanf("%d", &n);
    num.resize(n + 3);
    segTree.resize(4 * n);
    for (i = 1; i <= n; i++)
        scanf("%lld", &num[i]);
    makeSegTree(1, 1, n);
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        int a;
        scanf("%d", &a);
        if (a == 1) {
            int idx;
            ll value;
            scanf("%d %lld", &idx, &value);
            num[idx] = value;
            updateSegTree(1, 1, n, idx);
        }
        else if (a == 2) {
            int s, e;
            scanf("%d %d", &s, &e);
            printf("%lld\n", query(1, 1, n, s, e));
        }
    }
    return 0;
}