[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)

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

5817번: 고통받는 난쟁이들

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

 

1. 난쟁이들의 키를 입력 받고, 난쟁이들의 키를 인덱스로, 난쟁이들의 위치를 값으로하는 세그먼트 트리를 만듭니다.

 

2. 각 노드에는 구간의 최댓값과 최솟값을 각각 저장합니다.

 

3. 해당 구간의 최댓값과 최솟값의 차이가 Y - X와 같다면 YES를 아니라면 NO를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int N, M;
pair<int,int> segTree[524444];
int arr[200000];
int Min, Max;
 
void updateTree(int node, int s, int e, int idx, int n)
{
    if (idx < s || e < idx) return;
    if (s == e) {
        segTree[node] = { n, n };
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, idx, n);
    updateTree(node * 2 + 1, m + 1, e, idx, n);
 
    segTree[node].first = max(segTree[node * 2].first, segTree[node * 2 + 1].first);
    segTree[node].second = min(segTree[node * 2].second, segTree[node * 2 + 1].second);
}
 
void getTree(int node, int s, int e, int sidx, int eidx)
{
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        Min = min(Min, segTree[node].second);
        Max = max(Max, segTree[node].first);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, sidx, eidx);
    getTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        updateTree(1, 1, N, arr[i], i);
    }
 
    for (int i = 0; i < M; i++) {
        int cmd, X, Y;
        scanf("%d %d %d", &cmd, &X, &Y);
 
        if (cmd == 1) {
            updateTree(1, 1, N, arr[Y], X);
            updateTree(1, 1, N, arr[X], Y);
            swap(arr[X], arr[Y]);
        }
        else {
            Min = 987654321;
            Max = 0;
            getTree(1, 1, N, X, Y);
 
            if (Y - X == Max - Min) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
    }
}