백준 14428번 [수열과 쿼리 16](C++)-yes6686- 티스토리

백준 문제 풀이: 14428 [수열과 쿼리 16]

---

문제 링크: https://www.acmicpc.net/problem/14428

문제 설명:

수열이 주어질 때, 다음과 같은 두 가지 쿼리를 처리하는 프로그램을 작성합니다:

• 1 x y: 수열의 x번째 원소를 y로 변경합니다.
• 2 x y: 수열의 x번째 원소부터 y번째 원소까지 중 가장 작은 값의 인덱스를 출력합니다. (1부터 시작하는 인덱스 기준)

만약 최소값이 여러 개인 경우, 인덱스가 가장 작은 값을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long int arr[1000001];
struct Seg {
    int idx;
    int mi;
};

Seg seg[400001];
Seg go(int n, int s, int e) {
    if (s == e) {
        seg[n].mi = arr[s];
        seg[n].idx = s;
        return seg[n];
    } else {
        int mid = (s + e) / 2;
        Seg left = go(2 * n, s, mid);
        Seg right = go(2 * n + 1, mid + 1, e);
        if (left.mi < right.mi) {
            seg[n].mi = left.mi;
            seg[n].idx = left.idx;
        } else if (left.mi > right.mi) {
            seg[n].mi = right.mi;
            seg[n].idx = right.idx;
        } else {
            if (left.idx < right.idx) {
                seg[n].mi = left.mi;
                seg[n].idx = left.idx;
            } else {
                seg[n].mi = right.mi;
                seg[n].idx = right.idx;
            }
        }
        return seg[n];
    }
}

Seg ans;
Seg fi(int n, int s, int e, int l, int r) {
    if (e < l || r < s) return ans;
    if (l <= s && r >= e) {
        return seg[n];
    }
    int mid = (s + e) / 2;
    Seg left = fi(n * 2, s, mid, l, r);
    Seg right = fi(n * 2 + 1, mid + 1, e, l, r);
    if (left.mi < right.mi) {
        ans.mi = left.mi;
        ans.idx = left.idx;
    } else if (left.mi > right.mi) {
        ans.mi = right.mi;
        ans.idx = right.idx;
    } else {
        if (left.idx < right.idx) {
            ans.mi = left.mi;
            ans.idx = left.idx;
        } else {
            ans.mi = right.mi;
            ans.idx = right.idx;
        }
    }
    return ans;
}

Seg change(int n, int s, int e, int i, int d) {
    if (i < s || i > e) return seg[n];
    if (s == e) {
        seg[n].idx = s;
        seg[n].mi = d;
        return seg[n];
    }
    if (s != e) {
        int mid = (s + e) / 2;
        Seg left = change(n * 2, s, mid, i, d);
        Seg right = change(n * 2 + 1, mid + 1, e, i, d);
        if (left.mi < right.mi) {
            seg[n].mi = left.mi;
            seg[n].idx = left.idx;
        } else if (left.mi > right.mi) {
            seg[n].mi = right.mi;
            seg[n].idx = right.idx;
        } else {
            if (left.idx < right.idx) {
                seg[n].mi = left.mi;
                seg[n].idx = left.idx;
            } else {
                seg[n].mi = right.mi;
                seg[n].idx = right.idx;
            }
        }
        return seg[n];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    go(1, 0, n - 1);
    cin >> m;
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            arr[b - 1] = c;
            change(1, 0, n - 1, b - 1, c);
        } else if (a == 2) {
            ans.idx = 100001;
            ans.mi = 1000000001;
            cout << fi(1, 0, n - 1, b - 1, c - 1).idx + 1 << '\n';
        }
    }
}

---

코드 설명

• 세그먼트 트리 구성: 각 노드는 해당 구간에서 최소값과 그 최소값의 인덱스를 저장합니다.
• 구간 최소값 쿼리: 구간에서 최소값과 인덱스를 반환합니다. 최소값이 같으면 인덱스가 더 작은 것을 선택합니다.
• 값 변경: 세그먼트 트리를 갱신하여 쿼리 결과가 정확하도록 유지합니다.

시간 복잡도

세그먼트 트리의 빌드 및 각 쿼리의 시간 복잡도는 O(log n)입니다. 따라서 총 시간 복잡도는 O((n + m) log n)입니다.

---

결과

이 코드는 주어진 수열에서 최소값 쿼리와 값 변경 작업을 빠르게 처리합니다. 세그먼트 트리의 활용을 통해 효율적으로 문제를 해결할 수 있었습니다. 다른 개선 사항이 있다면 공유 부탁드립니다!