[백준] 디지털 비디오 디스크(DVDs)

해당 문제는 선택된 범위 내에 범위의 숫자가 모두 존재하는지를 확인하는 문제이다.

1~100 까지의 선반이 준비되어 있다면 처음에는 [1선반:1, 2선반: 2] 식으로 초기화 되어 있다.
그리고 다음 두가지 분기가 존재한다.

• 주어지는 범위 내에 범위의 숫자가 모두 있는지 확인
• 주어진 두 선반의 숫자를 교환

이때 첫번째 조건을 확인하기 위한 방법으로 최소,최댓값을 활용할 수 있다.
특정 범위의 숫자중 이외의 숫자가 포함될 경우 반드시 최소값 혹은 최대값이 해당 범위와 불일치하는 상황이 발생하는 점을 떠올릴 수 있다면 쉽게 풀 수 있다.

세크먼트 트리로 풀어내기 위해 조건을 어떻게 최적화 할지를 빠르게 캐치하는게 중요 포인트인 문제로 생각된다.

#include <iostream>

using namespace std;

struct S {
	int min;
	int max;
};

//리프 노드가 최대 10만개가 되어야함
S seg_tree[1 << 18]{};
int nums[100'001];

S init_tree(int left,int right,int depth,S* seg_tree) {
	if (left == right) {
		nums[left] = left; // 업데이트시 스왑정보를 활용하기 위해 초기화
		return seg_tree[depth] = { left,right };
	}

	int mid = (left + right) / 2;

	S set1 = init_tree(left, mid, depth * 2, seg_tree);
	S set2 = init_tree(mid + 1, right, depth * 2 + 1, seg_tree);

	int min = (set1.min < set2.min ? set1.min : set2.min);
	int max = (set1.max > set2.max ? set1.max : set2.max);

	return seg_tree[depth] = { min,max};
}

S update(int left, int right,int target1,int target2, int depth, S* seg_tree) {
	if (target1 > right || target2 < left) return seg_tree[depth]; //스완 하는 위치 이외의 탐색 범위 스킵
	if (target1<left && target2>right) return seg_tree[depth]; //스왑 하는 위치 이내의 탐색 범위 스킵
	if (left == right) {//nums 배열에 스왑되어진 숫자로 업데이트
		if (target2 == left) return seg_tree[depth] = { nums[target2],nums[target2] };
		if (target1 == left) return seg_tree[depth] = { nums[target1],nums[target1] };
	}

	int mid = (left + right) / 2;

	S set1 = update(left, mid, target1, target2, depth * 2, seg_tree);
	S set2 = update(mid + 1, right, target1, target2, depth * 2 + 1, seg_tree);

	//범위 최대 최소값 업데이트
	int min = (set1.min < set2.min ? set1.min : set2.min);
	int max = (set1.max > set2.max ? set1.max : set2.max);

	return seg_tree[depth] = { min,max };
}

S search(int left, int right, int start, int end, int depth, S* seg_tree) {
	if (start > right || end < left) return {100'001,0}; // 범위 이외의 탐색 스킵
	if (start<=left && end>=right) return seg_tree[depth]; // 범위 이내의 값 호출

	int mid = (left + right) / 2;

	S set1 = search(left, mid, start, end, depth * 2, seg_tree);
	S set2 = search(mid + 1, right, start, end, depth * 2 + 1, seg_tree);

	int min = (set1.min < set2.min ? set1.min : set2.min);
	int max = (set1.max > set2.max ? set1.max : set2.max);

	return { min,max };
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int T, N, K;
	cin >> T;
	
	while (T--) {
		cin >> N >> K;
		init_tree(0, N, 1, seg_tree);
		
		int q, a, b;
		while (K--) {
			cin >> q >> a >> b;
			if (q == 0) {
				//주어진 위치 숫자 스왑
				int set = nums[a];
				nums[a] = nums[b];
				nums[b] = set;
				update(0, N, a, b, 1, seg_tree);
			}
			else {
				S result = search(0, N, a, b, 1, seg_tree);
				cout << (result.min == a && result.max == b ? "YES\n" : "NO\n");
			}
		}
	}
	
}