BOJ)14428 수열과 쿼리 16

문제: icpc.me/14428

i j 가 주어질 때 Ai ~ Aj 까지의 최솟값의 인덱스를 출력하는 문제이다.

세그먼트 트리를 이용하여 구간의 가장 작은 위치의 인덱스를 저장해주면 된다.

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
int n, m, seg[400000], x, y, z, a[100001];
int uquery(int pos, int node, int x, int y) {
    if (pos < x || y < pos)return seg[node];
    if (x == y)return seg[node] = x;
    else {
        int mid = (x + y) >> 1;
        int q1 = uquery(pos, node * 2, x, mid);
        int q2 = uquery(pos, node * 2 + 1, mid + 1, y);
        if (q1 == -1 && q2 == -1)return -1;
        else if (q1 == -1)return seg[node] = q2;
        else if (q2 == -1)return seg[node] = q1;
        else if (a[q1] <= a[q2])return seg[node] = q1;
        else return seg[node] = q2;
    }
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)return -1;
    if (lo <= x&&y <= hi)return seg[node];
    int mid = (x + y) >> 1;
    int q1 = query(lo, hi, node * 2, x, mid);
    int q2 = query(lo, hi, node * 2 + 1, mid + 1, y);
    if (q1 == -1)return q2;
    if (q2 == -1)return q1;
    if (a[q1] <= a[q2])return q1;
    return q2;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
        uquery(i, 1, 1, n);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if (x == 1) {
            a[y] = z;
            uquery(y, 1, 1, n);
        }
        else
            printf("%d\n", query(y, z, 1, 1, n));
    }
    return 0;
}