[BOJ 9345]

문제 바로가기 : https://www.acmicpc.net/problem/9345
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

segment tree

세그먼트 트리 구현과 설명은 여기에 잘 설명이 돼있다. 참고 권장!

배열에 N개의 원소를 넣은 후 [A, B]의 구간합을 구한다고 해보자. (1<=A, B<=N)
N의 크기가 크지 않다면 A에서 B까지 하나씩 더해가며 계산해도 된다. O(N)에 답을 구할 수 있다.
세그먼트 트리를 이용하면 O(logN)만에 구할 수 있게 된다. 응용하면 구간에서 합 말고도 곱, 최댓값, 최솟값을 얻을 수 있다.

하지만 이름이 트리인 것처럼 기존의 배열을 참조해서 또 다른 배열을 만들어서 사용한다.
이진 트리로 구성되는데 힙 구조를 떠올리면 되겠다. 자식에서 부모로 접근하려면 인덱스/2를 해주면 된다.
세그먼트 트리를 구성하는데 O(N)이 걸리므로 쿼리를 여러번 수행할 일이 있다면 효율적으로 사용할 수 있겠다.

review

세그먼트 트리 구현은 대부분 비슷하므로 자세한 설명보다는 구현하다가 실수했던 부분을 써보려고 한다.
먼저 이 문제는 N-1번까지 오름차순으로 나열되어 있을 때 2가지 원소 값을 바꾸는 행위를 한다.
그리고 주어진 구간에서 순서와 상관없이 값 보존 여부에 따라 참/거짓을 출력해야 한다.

맨 처음에 떠오른 방법은 구간합이었는데 생각보다 간단할거 같아서 신나게 구현을 했다. 그렇게 시간을 신나게 날렸다.
반례가 있다. 2~4번을 체크하는데 조작을 겁나게 해서 [1, 3, 5]가 있다면 [2, 3, 4]와 합이 같다. 근데 참을 반환한다.
이런 일이 있으면 안된다. [2, 3, 4]를 보장할 수 있는 방법이 필요하다.
근데 생각해보면 [2, 3, 4]의 순서를 모르는 상태에서 보장할 수 있으려면 그렇게 방법이 많지 않다.
특정 위치의 값을 픽스해서 계산할 수가 없다. 합도 안된다. 그래서 최소, 최대를 이용하는 방법을 떠올렸다.
구간 A~B에서 최소가 되는 값은 A, 최대가 되는 값은 B여야 한다. 그렇지 않으면 조건을 만족하지 않는다.

//[A, B] 체크
if (searchMin(0, N - 1, 1, A, B) == A && searchMax(0, N-1, 1, A, B) == B) cout << "YES" << '\n';
else cout << "NO" << '\n';

최대, 최소를 이용해야 하니 각각 맞는 트리를 만들어주고(maxtree, mintree) 쿼리를 수행하면 된다.
순서를 바꾸는 쿼리를 수행할 때는 트리를 만들기 전에 값을 저장했던 배열 a[]에서 값을 가져와서 이용했다.
세그먼트 트리를 만들었지만 여기서 값을 가져오면 O(logN)이 걸린다.
O(1)만에 가져오려면 배열을 이용하는게 편하다.

//순서 바꾸기
if (Q == 0) {
    maxUplast_modified_at(0, N-1, 1, A, a[B]);
    maxUplast_modified_at(0, N-1, 1, B, a[A]);
    minUplast_modified_at(0, N-1, 1, A, a[B]);
    minUplast_modified_at(0, N-1, 1, B, a[A]);
    swap(&a[A], &a[B]);
}

예전에(라고 해봐야 1~2달 전) 처음 접했을 때는 낑낑대면서 겨우 이해하고 결국엔 포기한 채로 냅뒀던 파트였는데
공부량이 좀 쌓이고 나서 보니까 그렇게 겁먹을 필요는 없었구나 생각이 든다. 다행이당