백준[14428] 수열과 쿼리 16

문제 설명

문제 링크

http://icpc.me/14428

풀이

세그먼트 트리 문제다.

세그먼트 트리에 최솟값을 저장할 때, 인덱스도 포함하여 저장하면 된다.

cf) 나는 min도 구현을 해서 사용했지만, stl에 있는 min()을 그냥 사용해도 된다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;

int arr[100005];
pii tree[400005];

pii min(pii &a, pii &b) {
    if (a.first < b.first) return a;
    if (a.first == b.first) {
        if (a.second < b.second) return a;
        else return b;
    }
    else return b;
}

pii query(int node, int s, int e, int qs, int qe) {
    if (e < qs || qe < s) return {1e9, 1e9};
    if (qs <= s && e <= qe) return tree[node];
    int mid = (s + e) >> 1;
    return min(query(2 * node, s, mid, qs, qe), query(2 * node + 1, mid + 1, e, qs, qe));
}

void update(int node, int s, int e, int idx, int num) {
    if (e < idx || idx < s) return;
    if (s == e) {
        tree[node] = {num, idx};
        return;
    }
    int mid = (s + e) >> 1;
    update(2 * node, s, mid, idx, num);
    update(2 * node + 1, mid + 1, e, idx, num);    
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

void init(int node, int s, int e) {
    if (s == e) {
        tree[node] = {arr[s], s};
        return;
    }
    int mid = (s + e) >> 1;
    init(2 * node, s, mid);
    init(2 * node + 1, mid + 1, e);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", arr + i);
    init(1, 0, 1e5);
    int q; scanf("%d", &q);
    while (q--) {
        int t, a, b; scanf("%d %d %d", &t, &a, &b);
        if (t == 1) {
            update(1, 0, 1e5, a, b);
        } else {
            printf("%d\n", query(1, 0, 1e5, a, b).second);
        }
    }
}