C++[백준]9345번 디지털 비디오 디스크(DVDs)

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

9345번: 디지털 비디오 디스크(DVDs)

 

솔루션

---

일반적인 구간 세그먼트 트리를 생각헀다가 해법을 떠올리기 힘들어서 꽤나 고생했다..

결국은 세그먼트트리를 두개를 이용해서 문제를 해결 할 수 있는 아이디어를 얻었다.

한개는 구간에서의 최대값을 저장하는 세그먼트트리, 다른 한개는 구간의 최소값을 저장하는 세그면트 트리를 이용하였다.

 

1) 각 배열에 arr[i] = i 로 값을 채워주고 min, max 세그먼트 트리를 만든다.

2) Q와 a,b를 입력받고 아래의 과정을 걸친다.

 2-1) Q가 0이면, swap(arr[a],arr[b])를 해 주고, 세그먼트 트리를 갱신한다.

 2-1) Q가 1이면, 구간의 최대 최소값을 구하고 최소값과 a가 같고, b와 최대값이 같으면 YES를 출력하고 아니면 No를 출력한다.

 

최대 최소 값으로 어떻게 답을 도출 해 낼 수 있는지 예를 들어 설명하면 세가지 경우로 볼 수 있다.

 

특정 구간 l,r이 있을 때 a,b를 바꿀 때,

 

1) (l<= a <=b <= r) 인 경우

 구간 내에서 바뀌기 때문에  구간에서의 최대 최소가 변하지 않는다.

 따라서 손님은 DVD를 무사히 빌려 갈 수 있다.

 

2) (a< l <= b <= r) 인 경우

 a가 l보다 작은 값에서 바뀌었기 때문에  구간 l, r 사이에 최소 값이 변하게 된다.

 따라서 DVD를 빌릴 수 없다.

 

 

3) (l<=a<=r<b) 인 경우

 b가 r보다 크므로 구간 l, r 사이에 최대값이 변하게 되어 DVD를 빌릴 수 없다.

 

min-max 세그먼트 트리를 이렇게 변형해서 문제를 만드는 게 너무 신기하다..

 

코드

---

#define pii pair<int,int>
#define INF 987654321
#include <iostream>
using namespace std;

int minseg[400002];
int maxseg[400002];
int arr[100002];
int N,M;

void update(int node){
	maxseg[node] = max(maxseg[node * 2], maxseg[node * 2 + 1]);
	minseg[node] = min(minseg[node * 2], minseg[node * 2 + 1]);
	return;
}

void makeSeg(int str, int end, int node) {
	if (str == end) {
		minseg[node] = arr[str];
		maxseg[node] = arr[str];
		return;
	}
	else {
		int mid = (str + end) / 2;
		makeSeg(str, mid, node * 2);
		makeSeg(mid + 1, end, node * 2 + 1);
		update(node);
		return;
	}
}

void UpdateSeg(int str, int end, int node, int idx) {
	if (str == end) {
		minseg[node] = arr[str];
		maxseg[node] = arr[str];
	}
	else {
		int mid = (str + end) / 2;
		
		if (idx <= mid) {
			UpdateSeg(str, mid, node * 2, idx);
		}
		else {
			UpdateSeg(mid + 1, end, node * 2 + 1, idx);
		}
		update(node);
	}
	return;
}

pii getRange(int str, int end, int l, int r, int node) { //{큰 값, 작은 값}
	if (str > r || end < l) return { -INF,INF };
	if (str >= l && end <= r) return { maxseg[node],minseg[node] };
	int mid = (str + end) / 2;
	pii tmp1 = getRange(str, mid, l, r, node * 2);
	pii tmp2 = getRange(mid + 1, end, l, r, node * 2 + 1);
	return { max(tmp1.first,tmp2.first),min(tmp1.second,tmp2.second) };
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int tc;
	cin >> tc;
	while (tc--) {
		cin >> N >> M;
		for (int i = 0; i < N; i++) {
			arr[i] = i;
		}
		makeSeg(0, N - 1, 1);


		for (int i = 0; i < M; i++) {
			int Q, a, b;
			cin >> Q >> a >> b;
			//a--; b--;
			if (Q == 0) {//선반 바꿔끼우기.
				swap(arr[a], arr[b]);
				UpdateSeg(0, N - 1, 1, a);
				UpdateSeg(0, N - 1, 1, b);
			}
			else { //책을 빌리기
				pii ans = getRange(0, N - 1, a, b, 1);
				
				if (ans.first == b && ans.second == a) {
					cout << "YES\n";
				}
				else cout << "NO\n";
			}
		}
		
	}
}