백준 9345: 디지털 비디오 디스크(DVDs)
문제 요약
N개의 DVD들로 구성된 시리즈가 있다. (각 DVD들은 0번부터 N-1 까지 이루어져 있고,
선반의 번호 또한 0번부터 N-1 까지 이루어져 있다). DVD를 진열할 때 i번 DVD는 i번 선반에 진열을 한다.
이에 대해 다음의 프로그램을 작성하려고 한다.
1. 손님이 L번 선반부터 R번 선반까지에 있는 DVD들을 가져 왔을때 실제로 DVD가 L번부터 R번까지 있나 확인을 해 줄 수 있다.
2. DVD의 순서는 상관이 없다. 예를 들어 손님이 2번 선반부터 4번 선반까지에 있는 DVD를 가져왔을 때 DVD가 2, 3, 4 순서로 진열되어 있건, 4, 2, 3 순서로 진열되어 있건 상관이 없다는 얘기다. 즉 L번부터 R번까지의 DVD가 있으면 된다.
문제의 단순화를위해 고객이 DVD를 빌려가면, 그 즉시 시청한뒤 바로 반납한다고 가정한다. 또한 가져다 놓는 위치는 빌리기 전과 동일하다(4, 3, 2 순서로 진열되어 있었으면 다시 4, 3, 2 순서로 진열한다).
문제 분류
자료 구조세그먼트 트리
문제 풀이
이 문제를 해결할 때 주요 포인트는 두 개의 세그먼트 트리를 이용하는 것이다. 하나는 최소 연산을, 다른 하나는 최대 연산을 수행한다.
[L, R] (L <= R)의 구간에서 순서 상관 없이 L~R까지의 DVD가 있는지 확인하려면, [L, R]사이의 구간의 최솟값이 L이고, 최댓값이 R인지 확인하면 된다. 둘 중 하나라도 아니라면 [L, R]구간에 다른 값 하나가 들어와있는 것이다.
그렇다면 이를 어떻게 구현할 수 있을까? 생각의 전환이 필요하다. 세그먼트 트리의 리프노드의 인덱스를 DVD번호, 값을 위치로 표현하는 것이 아니라, 인덱스를 위치, 값을 DVD의 번호로 설정한다. 그리고 [L, R]의 구간에서 시리즈가 L~R인지 검사하는 것이 아니라, 시리즈가 L~R의 범위인 번호가 [L, R]의 범위에 정확히 있는지 확인한다. 이 둘은 같은 것을 의미하지만, 접근법은 다르다.
즉, 0번 DVD는 세그먼트 트리의 리프 노드 중 seg[i] = 0인 i번째에 있을 것이다. seg[0] = i가 아니다.
위의 방식으로 세그먼트 트리를 구축한 후, 입력 q, a, b에 대해 q == 0이면, a와 b의 위치인 aLoc과 bLoc을 최댓값 세그먼트 트리를 통해 받아온다. 이는 최소의 세그먼트 트리여도 상관없다.
그 후 최소 트리 및 최대 트리의 값에 대해, a의 위치를 bLoc으로, b의 위치를 aLoc으로 업데이트한다.
q == 1이면, [a, b] 구간에서 최솟값이 a이고 최댓값이 b인지 검사한다. 맞다면 [a, b]번호의 DVD가 [a, b]구간에 연속적으로 선반에 존재한다는 뜻이 된다.
풀이 코드
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int seg[400000], seg2[400000];
int construct(int l, int r, int idx)
{
if (l == r) seg[idx] = l;
else {
int mid = (l + r) / 2;
seg[idx] = min(construct(l, mid, idx * 2 + 1), construct(mid + 1, r, idx * 2 + 2));
}
return seg[idx];
}
int construct2(int l, int r, int idx)
{
if (l == r) seg2[idx] = l;
else {
int mid = (l + r) / 2;
seg2[idx] = max(construct2(l, mid, idx * 2 + 1), construct2(mid + 1, r, idx * 2 + 2));
}
return seg2[idx];
}
int update(int l, int r, int idx, int loc, int val)
{
if (loc < l || loc > r) return seg[idx];
if (l == r) {
if (l == loc) seg[idx] = val;
}
else {
int mid = (l + r) / 2;
seg[idx] = min(update(l, mid, idx * 2 + 1, loc, val), update(mid + 1, r, idx * 2 + 2, loc, val));
}
return seg[idx];
}
int update2(int l, int r, int idx, int loc, int val)
{
if (loc < l || loc > r) return seg2[idx];
if (l == r) {
if (l == loc) seg2[idx] = val;
}
else {
int mid = (l + r) / 2;
seg2[idx] = max(update2(l, mid, idx * 2 + 1, loc, val), update2(mid + 1, r, idx * 2 + 2, loc, val));
}
return seg2[idx];
}
int Min(int start, int end, int l, int r, int idx)
{
if (r < start || l > end) return 100001;
if (start <= l && r <= end) return seg[idx];
int mid = (l + r) / 2;
return min(Min(start, end, l, mid, idx * 2 + 1), Min(start, end, mid + 1, r, idx * 2 + 2));
}
int Max(int start, int end, int l, int r, int idx)
{
if (r < start || l > end) return -1;
if (start <= l && r <= end) return seg2[idx];
int mid = (l + r) / 2;
return max(Max(start, end, l, mid, idx * 2 + 1), Max(start, end, mid + 1, r, idx * 2 + 2));
}
int main()
{
int t, n, k, q, a, b;
cin >> t;
while (t--)
{
scanf("%d%d", &n, &k);
construct(0, n - 1, 0);
construct2(0, n - 1, 0);
for (int i = 0; i < k; i++) {
scanf("%d%d%d", &q, &a, &b);
if (q == 0) {
int aLoc = Max(a, a, 0, n - 1, 0);
int bLoc = Max(b, b, 0, n - 1, 0);
update(0, n - 1, 0, a, bLoc);
update2(0, n - 1, 0, a, bLoc);
update(0, n - 1, 0, b, aLoc);
update2(0, n - 1, 0, b, aLoc);
}
else {
if (a == Min(a, b, 0, n - 1, 0) && b == Max(a, b, 0, n - 1, 0))
printf("YES\n");
else printf("NO\n");
}
}
}
return 0;
}