백준 6218번 [Balanced Lineup](C++)-yes6686- 티스토리

백준 문제 풀이: 6218 [Balanced Lineup]

---

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

문제 설명:

주어진 소 구간에 대해 최대 값과 최소 값의 차이를 구하는 문제입니다. 이를 빠르게 계산하기 위해 세그먼트 트리를 사용합니다.

---

문제 해결 코드

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

int arr[100001];

struct Seg {
    int ma;
    int mi;
};

Seg seg[400001];

Seg go(int n, int s, int e) {
    if (s == e) {
        seg[n].ma = arr[s];
        seg[n].mi = arr[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);
        seg[n].ma = max(left.ma, right.ma);
        seg[n].mi = min(left.mi, right.mi);
        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);
    ans.ma = max(left.ma, right.ma);
    ans.mi = min(left.mi, right.mi);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    go(1, 0, n - 1);
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        ans.ma = 0;
        ans.mi = 1000000000;
        cout << fi(1, 0, n - 1, a - 1, b - 1).ma - fi(1, 0, n - 1, a - 1, b - 1).mi << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 사용하여 구간의 최대 값과 최소 값을 빠르게 구합니다.
• 구현 세부사항:
  • go 함수: 세그먼트 트리를 초기화하여 각 구간의 최대 값과 최소 값을 계산합니다.
  • fi 함수: 주어진 구간 [l, r]에 대해 최대 값과 최소 값을 반환합니다.
  • 최종적으로, 구간 최대 값에서 최소 값을 뺀 결과를 출력합니다.
• 시간 복잡도: O(log n) per query
  • 세그먼트 트리 초기화: O(n)
  • 구간 최대/최소 값 질의: O(log n)

---

결과

세그먼트 트리를 사용하여 구간의 최대 값과 최소 값을 빠르게 구함으로써 문제를 해결했습니다. 효율적인 구현을 통해 큰 입력 크기에서도 빠르게 실행 가능합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!