c++ 2912번 백설공주와 난쟁이 (백준)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//입력을 받을 배열, merge sort tree을 구성할 vector들
int arr[300001];
vector<int> tree[1200001];

void update(int s, int e, int node, int index, int val) { //merge sort tree 수정
	if(s > index || e < index) return;
	tree[node].push_back(val);
	if(s==e) return;
	int m = (s+e)/2;
	update(s, m, node*2, index, val);
	update(m+1, e, node*2+1, index, val);
}

int find(int s, int e, int node, int l, int r, int key) { //merge sort tree에서 key값 이하인 요소들 반환
	if(s > r || e < l) return 0;
	if(l <= s && e <= r) {
		//upper_bound
        //본래 목적은 오름차순 정렬데이터에서 key값 보다 크면서, 가장 먼저 나오는 데이터의 index을 알기 위해서
        //여기서 구한 index는 key값 이하의 개수와 같은 의미를 가집니다.
		int left=0, right=tree[node].size(), mid;
		while(left < right) {
			mid = (left+right)/2;
			if(tree[node][mid] <= key) left = mid+1;
			else right = mid;
		} return right;
	}
	int m = (s+e)/2;
	return find(s, m, node*2, l, r, key) + find(m+1, e, node*2+1, l, r, key);
}

int main(void) {
	int n, c, m;
	scanf("%d %d", &n, &c);
	
	for(int i=1; i<=n; i++) { //요소들 입력받기
		scanf("%d", &arr[i]);
		update(1, n, 1, i, arr[i]);
	}
	
	for(int i=1; i<=1200000; i++) { //merge sort tree의 모든node 오름차순 sort
		sort(tree[i].begin(), tree[i].end());
	}
	
	scanf("%d", &m);
	while(m--) { //query
		int a, b;
		scanf("%d %d", &a, &b); //쿼리 입력
		
        //이진탐색 left = 1, right = 색깔 최대치
        //merge sort tree의 find()을 이용해서 특정 구간에서 1부터 mid까지의 색깔이 얼마나 있는지를 확인한다음
        //절반 이하이면 left = mid+1  을
        //절반 초과면 여기서 특정 구간에서 1부터 mid-1까지의 색깔이 얼마나 있는지를 확인한 다음
        //특정 구간에는 mid와 같은 색깔이 몇개인지를 그리고 그 개수가 half 이하이면 right = mid -1;
        //half 초과이면 이것이 답이 되며, 그때의 색깔을 따로 저장한 다음 이분탐색을 정지합니다.
		int half = (b-a+1)/2;
		int left = 1, right = c, mid, isYes = 0;
		while(left <= right) {
			mid = (left+right)/2;
			int tmp = find(1, n, 1, a, b, mid);
			if(tmp <= half) left = mid + 1;
			else {
				if(tmp - find(1, n, 1, a, b, mid-1) <= half) right = mid - 1;
				else {
					isYes = mid;
					break;
				}
			}
		}
		
		if(isYes) printf("yes %d\n", mid);
		else printf("no\n");
	}
}

 

풀이 : merge sort tree, upper_bound, 이분탐색

 

1. merge sort tree을 위한 배열과 벡터들을 자동 할당합니다.

2. N, C을 입력 받습니다.

3. N개의 요소들을 입력 받고, 이 요소들로 merge sort tree 을 구성합니다.

4. merge sort tree 의 모든 node 들을 오름차순 정렬합니다.

5. 쿼리의 개수를 입력 받습니다.

6. 하나의 쿼리 마다 주어진 구간에 대해서, 이분탐색을 이용하여 하나의 색깔이 구간의 절반을 초과할 만큼 존재하는 것이 존재하는지를 파악합니다.

있다면 yes 하고 그 색깔의 번호를 없다면 no 을 출력합니다.

 

6. 자세히 (이분탐색)

 

//이진탐색 left = 1, right = 색깔 최대치

//merge sort tree의 find()을 이용해서 특정 구간에서 1부터 mid까지의 색깔이 얼마나 있는지를 확인한다음

//절반 이하이면 left = mid+1  을

(절반이하이기 때문에 1부터 mid까지의 색깔에서는 절대로 절반을 초과할 만큼 같은 색깔이 존재할수가 없다!)

//절반 초과면 여기서 특정 구간에서 1부터 mid-1까지의 색깔이 얼마나 있는지를 확인한 다음

(색깔이 mid인 것만의 개수를 알기 위해서)

 

//특정 구간에는 mid와 같은 색깔이 몇개인지를 그리고 그 개수가 half 이하이면 right = mid -1;

(다음에 탐색하는 색깔의 번호는 지금의 mid보다 감소하지만, 1부터 다음 mid까지의 색깔로 이루어진 개수가 절반을 넘을 가능성은 존재하며, 거기서 다음 mid의 색깔이 절반을 초과할 경우가 존재하므로 right을 변경합니다. )

//half 초과이면 이것이 답이 되며, 그때의 색깔을 따로 저장한 다음 이분탐색을 정지합니다.

(찾았기 때문에 while문이 종료 될 때까지 기다릴 이유는 없습니다)

 

색깔의 개수는 upper_bound을 이용해서 구했습니다.

 

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

2912번: 백설공주와 난쟁이