개요

백준 9345번: 디지털 비디오 디스크

• 입력
  첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. (T ≤ 20 인 자연수)

  각각의 테스트 케이스 첫 번째 줄에는 DVD들의 수를 의미하는 정수 N 과 대여점에서 일어나는 사건의 수를 의미하는 정수 K 가 주어진다. (1 ≤ N ≤ 100,000 , 1 ≤ K ≤ 50,000)

  이어서 대여점에서 일어나는 사건 K 개가 주어진다. 각각의 줄은 세 정수 Q, A, B 을 포함한다. (Q는 0또는 1이고, 0 ≤ A ≤ B < N )

  Q는 0 일때, 진상 손님 진일이가 선반 A의 DVD와 선반 B의 DVD를 서로 바꿔 끼우는 사건을 의미한다.

  Q가 1 일때는 손님이 선반 A부터 선반 B에 있는 DVD를 카운터에 가져오는 사건을 의미한다. 위에서도 언급했듯이 이 사건이 DVD들의 위치를 바꾸는 일은 일어나지 않는다.

• 출력
  손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하고, 그렇지 않다면 "NO"를 출력한다.

접근 방식

1. 처음 생각한 방식은 크기도 10만이라 일단 세그먼트 트리를 이용한 후,
   리프노드에는 인덱스번째 선반에 몇번 dvd가 있는지를 저장했다.
   각 노드를 pair<int,int> 형으로 잡은 후, pair의 first는 해당 노드가 관리하는 구간의 증가하는 수열의 최솟값, second는 최대값을 저장하는식으로 짰다.

2. 수열이 뒤집어져도 답이므로 두 pair<int,int> left, right을 합치는 함수를

   pair<int,int > ret;
   //자식 노드 두개가 연속이라면 합치기 12 34/ 13 24
   if (left.second + 1 == right.first || (left.second >= right.first && left.first <= right.first && right.second >= left.second)
   	) {
   	ret.first = left.first;
   	ret.second = right.second;
   }
   //거꾸로 연속일수도 있음 67 45/ 57 46
   else if (right.second + 1 == left.first || (right.second >= left.first && right.first <= left.first && left.second >= right.second)) {
   	ret.first = right.first;
   	ret.second = left.second;
   }
   //자식 노드 두개가 불연속이라면 제일 긴 연속구간을 저장 
   else {
   	//왼쪽자식이 더 길면 왼쪽자식값으로 갱신
   	if (left.second - left.first >= right.second - right.first) {
   		ret = left;
   	}
   	//오른쪽 자식이 더 길면 오른쪽 자식값으로 갱신
   	else {
   		ret = right;
   	}
   }

   이런식으로 12 34/ 13 24/ 24 13 이렇게 되면 해당 구간 관리하는 pair에 {1,4}가 저장되도록 만들었다.
   하지만 문제에서 요구하는건 13 24 이런식으로 연속이 아무것도 안되더라도 {1,4}가 가능하지만 위의 코드대로 하면 그냥 {1,3}이 담겨버린다.

3. 검색해보니 이 문제는 리프노드의 인덱스를 선반, 값을 dvd번호로 설정하지말고,
   리프노드의 인덱스를 dvd번호, 값을 해당 dvd가 어떤 선반에 있는지로 설정을 해서 구현하는 문제였다.
   pair노드도 연속적인 수열의 최대 최소값이 아니라 해당 노드가 관리하는 구간의 최소, 최대값을 저장하면 된다.

4. 왜 연속되는 수열의 최소,최대값이 아닌 해당 구간의 최소,최대값만 저장하면 되나 생각해봤다.
   문제에선 47 65/ 45 67/ 57 64가 전부 연속하다고 간주한다.
   구간에 예를 들어 4 5 6 7을 저장한다 하면 최소값은 4, 최대값은 7이 저장된다.
   만약 최소값이 4 가 아니거나, 최대값이 7이 아니라면 해당 구간은 연속적이지 않다는 뜻이다.
   따라서 굳이 연속적인지 조건문으로 체크할거 없이 최소 최대값과
   원하는 쿼리의 최소 최대값을 비교만 하면 된다.

전체 코드

#include<iostream>
#include<vector>

//세그트리의 i번째 리프노드에는 현재 i번째 어떤 디스크 들어있냐가 아니라 i번째 디스크가 몇번 인덱스에 있는지를 조사해야됨.

using namespace std;
int N=0,K=0,firstLeafNodeIdx=1;
vector<pair<int, int>> segTree;
//이번문제는 0번쨰 인덱스를 포함하므로 빈 노드는 -1로 설정해야함
pair<int, int> BasePair = { -1, - 1 };

pair<int, int> CalculateMinAndMAx(pair<int, int> left, pair<int, int>right) {
	pair<int, int> ret;
	//left나 right가 비어있을 때 처리
	if (left == BasePair) {
		if (right == BasePair) return BasePair;
		else return right;
	}
	else if(right==BasePair) {
		return left;
	}
	//ret에는 left,right의 최소 최대를 가져와서 저장 
	ret.first = left.first > right.first ? right.first : left.first;
	ret.second = left.second > right.second ? left.second : right.second;

	return ret;
}

//[targetL, targetR]구간의 최소 최대값을 pair<int,int>형으로 반환
pair<int,int> IsDvdsExistInARow(int targetL,int targetR,int nodeNum,int curL,int curR) {
	if (curL > targetR || curR < targetL) return BasePair;
	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
	int mid = (curL + curR) / 2;
	return CalculateMinAndMAx(IsDvdsExistInARow(targetL, targetR, nodeNum*2,curL,mid),
		IsDvdsExistInARow(targetL,targetR,nodeNum*2+1,mid+1,curR));
}
//idx+firstLeafNodeIdx 인덱스 리포노드의 조상노드들을 갱신 
void SetAncestorNode(int idx) {
	int tmpIdx = idx + firstLeafNodeIdx;
	while (tmpIdx > 1) {
		tmpIdx /= 2;
		pair<int, int> left = segTree[tmpIdx * 2];
		pair<int, int> right = segTree[tmpIdx * 2+1];
		segTree[tmpIdx] = CalculateMinAndMAx(left, right);
	}
}

void Swap(int indexA, int indexB) {
	//같은 인덱스일때 오버헤드 제거
	if (indexA == indexB) return;
	swap(segTree[firstLeafNodeIdx + indexA],segTree[firstLeafNodeIdx+indexB]);
	SetAncestorNode(indexA);
	SetAncestorNode(indexB);
}

//Q에 따라 A,B 처리
void Solution(int Q,int A,int B) {
	if (Q == 0) {
		
		Swap(A, B);
	}
	else if (Q == 1) {
		pair<int, int> Ans = IsDvdsExistInARow(A, B, 1, 0, firstLeafNodeIdx - 1);
		if (Ans.first == A && Ans.second == B) {
			cout << "YES" << '\n';
			return;
		}
		else
			cout << "NO"<<'\n';
	}
}

void Input() {
	int testCase=0,Q=0,A=0,B=0;
	segTree.resize(524288);
	cin >> testCase;
	for (int i = 0; i < testCase; i++) {
		cin >> N >> K;
		while (firstLeafNodeIdx < N) firstLeafNodeIdx *= 2;
		//초기 세그먼트 트리 {-1,-1}로 세팅 
		fill(segTree.begin(), segTree.begin() + firstLeafNodeIdx * 2, BasePair);
		//초기에 i번째 dvd는 i번째 dvd가 꽂혀있으므로 초깃값 세팅 
		for (int j = 0; j < firstLeafNodeIdx; j++) {
			segTree[j + firstLeafNodeIdx] ={ j, j };

		}
		//조상노드들 세팅
		for (int j = 0; j < firstLeafNodeIdx; j++) {
			SetAncestorNode(j);
		}
		//쿼리값 받아서 처리 
		for (int j = 0; j < K; j++) {
			cin >> Q >> A >> B;
			Solution(Q, A, B);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

다른 문제와 달리 이번 문제는 0번째 인덱스를 포함하므로,
기본 리프노드를 0으로 초기화하면 비어있는 리프노드인데 0번째 인덱스를 포함하게 되므로

//이번문제는 0번쨰 인덱스를 포함하므로 빈 노드는 -1로 설정해야함
pair<int, int> BasePair = { -1, - 1 };

기본 페어를 처음에 선언해주고 구현하였다.