백준 14438 - 수열과 쿼리 17

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

 

배열의 값을 바꾸고 특정 구간의 최솟값을 물어보는 질의가 최대 10만건 들어온다.

 

세그먼트 트리를 통해 구간의 최솟값을 빠르게 계산하면 된다.

 

구간의 최솟값을 구할 때 구간을 벗어나는 범위는 INF로 처리해주면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int ar[100001];
int n;

inline int mid(int stt, int end) { return stt + (end - stt) / 2; }

int init(vector<int> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = ar[start];
    int m = mid(start, end);
    return tree[node] = min(init(tree, node * 2, start, m), init(tree, node * 2 + 1, m + 1, end));
}

int update(vector<int> &tree, int node, int start, int end, int idx, int num)
{
    if (idx < start || idx > end) return tree[node];
    if (start == end) return tree[node] = num;
    int m = mid(start, end);
    return tree[node] = min(update(tree, node * 2, start, m, idx, num), update(tree, node * 2 + 1, m + 1, end, idx, num));
}

int query(vector<int> &tree, int node, int start, int end, int l, int r)
{
    if (l <= start && end <= r) return tree[node];
    if (start > r || end < l) return 1e9 + 7;
    int m = mid(start, end);
    return min(query(tree, node * 2, start, m, l, r), query(tree, node * 2 + 1, m + 1, end, l, r));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    vector<int> segtree(n * 4);

    for (int i = 1; i <= n; ++i)
        cin >> ar[i];
    init(segtree, 1, 1, n);
    
    int q;
    cin >> q;
    while (q--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            ar[b] = c;
            update(segtree, 1, 1, n, b, c);
        }
        else
        {
            cout << query(segtree, 1, 1, n, b, c) << '\n';
        }
    }
}