c언어 9345번 디지털 비디오 디스크(DVDs) (백준)

#include <stdio.h>

int tree[2][400004]={};
int arr[100001]={};

int update(int s, int e, int node, int index, int dif, int isMax) { //isMax는 최소인지 최대인지를 구별하기 위한 변수입니다.
	if(s>index || e<index) return tree[isMax][node];
	if(s==e) return tree[isMax][node] = dif;
	int m=(s+e)/2;
	int l = update(s,m,node*2,index,dif, isMax);
	int r = update(m+1,e,node*2+1,index,dif, isMax);
	
	if(isMax == 0) return tree[isMax][node] = (l>r)?r:l; //최소
	else return tree[isMax][node] = (l>r)?l:r; //최대
}

int find(int s, int e, int node, int l, int r, int isMax) {
	if(s>r || e<l) { //범위를 넘어감
		if(isMax == 0) return 100001; //최소 세그먼트 트리 인 경우
		else return -1; //최대 세그먼트 트리인 경우
	}
	if(l<=s && e<=r) return tree[isMax][node];
	int m=(s+e)/2;
	int L = find(s,m,node*2,l,r,isMax);
	int R = find(m+1,e,node*2+1,l,r,isMax);

	if(isMax == 0) return (L>R)?R:L; //최소
	else return (L>R)?L:R; //최대
}

int main(void) {
	int t,n,k;
	scanf("%d",&t);
	while(t--) {
		scanf("%d %d",&n,&k);
		
		//init

		
		for(int i=0; i<=n; i++) {
			arr[i] = i;
			update(0,n,1,i,i,0);
			update(0,n,1,i,i,1);
		}
		
		while(k--) {
			int q,a,b;
			scanf("%d %d %d",&q,&a,&b);
			if(q==0) {
				int tmp = arr[a];
				arr[a] = arr[b];
				arr[b] = tmp;
				update(0,n,1,a,arr[a],0);
				update(0,n,1,a,arr[a],1);
				update(0,n,1,b,arr[b],0);
				update(0,n,1,b,arr[b],1);
			}
			else if(q==1) {
				printf("%s\n",(find(0,n,1,a,b,0)==a && find(0,n,1,a,b,1)==b) ? "YES" : "NO");
			}
		}
	}
}

 

풀이 : 세그먼트 트리

 

지정된 구간에 연속적으로 원하는 DVD들이 있는지를 파악하는 방법은

구간에 있는 DVD들의 최댓값과 최솟값을 확인하는 것 입니다.

 

0. 최댓값과 최솟값에 대한 세그먼트 트리를 만들어 놓습니다.

1. 0번부터 n번까지에 몇 번째 dvd가 있는지를 나태내는 배열을 만들어 놓습니다.

2. q=0이면 1에서 만들어논 배열에서 두 개의 값의 위치를 swap 하고 이를 세그먼트 트리에도 반영합니다.

3. q=1이면 입력된 구간과 최솟값 최댓값이 같은지를 확인합니다.

 

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