[BOJ/2912] 백설공주와 난쟁이, c++

www.acmicpc.net/problem/2912

2912번: 백설공주와 난쟁이

한줄 후기 : 세그 트리라도 푼게 어디야..

 

원래 확률적 알고리즘 파트라서 Mo's Algorithm 을 이용해 풀어봐야 하는 것 같다.

하지만.. 도저히 못풀겠음 구글링 좀 해서 봤는데 계속 시간 초과 나서 못 풀었다.

그래서 이 문제를 또 풀 수 있는 방법인 세그먼트 트리를 이용해 풀었다.

세그먼트 트리로 푸는 법은 간단하다. 

그냥 처음 트리를 생성할 때, 트리에는 해당 구간 내에 난쟁이들이 가장 많이 쓰고 있는 ( = 절반 넘게) 모자의 색상을 넣어주고, 만약 모든 색상이 절반을 넘지 못한다면, 그냥 -1을 넣는다.

그 후 구간 쿼리 a,b가 들어올 때 마다 세그먼트 트리를 돌면서 a~b 사이의 모자를 확인해 준다.  

 

 모자의 개수 cnt를 구하는 방법이 신기한데, 이 방법은 사실 내가 생각한건 아니고, 다른 분 설명을 참고해서 풀었다.

이진 탐색 upper_bound, lower_bound 를 이용한다.

모자 배열을 받을 때, 다른 vector idx에 해당 모자를 쓴 난쟁이들의 index를 함께 저장해둔다.

그리고 각 모자 색상 별 난쟁이 index를 정렬해준다.

 

이렇게 정렬하고 나서 특정 구간이 주어지고, idx 벡터에서 해당 구간(index)을 검색하면 나오는 upper(right) - lower(left) + 1 이 해당 구간 내에 그 모자를 쓴 난쟁이의 수가 됨을 알 수 있다. 

 

//AC
//BOJ 2912 백설공주와 난쟁이
#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 301010
using namespace std;
vector<int> idx[SIZE];
int arr[SIZE],  tree[SIZE*4];
int N, C;
void make(int node, int left, int right){
	if(left == right){
		tree[node] = arr[left];
		return;
	}
	int mid = (left+right) / 2;
	make(node*2, left, mid);
	make(node*2+1, mid+1, right);
	int lc = tree[node*2];
	int cnt = upper_bound(idx[lc].begin(), idx[lc].end(), right)-lower_bound(idx[lc].begin(), idx[lc].end(), left)+1; 
	if(cnt > (right-left+1)/2) {
		tree[node] = lc;
		return;
	}
	lc = tree[node*2+1];
	cnt = upper_bound(idx[lc].begin(), idx[lc].end(), right)-lower_bound(idx[lc].begin(), idx[lc].end(), left)+1; 
	if(cnt > (right-left+1)/2){
		tree[node] = lc;
		return;
	} 
	tree[node] = -1;
}
int segTree(int node, int left, int right, int start, int end){
	if(right<start || end < left)	return 0;
	if(start >= left && right >= end){
		int cnt = upper_bound(idx[tree[node]].begin(), idx[tree[node]].end(), right)-lower_bound(idx[tree[node]].begin(), idx[tree[node]].end(), left); 
		if(cnt > (right-left+1)/2){
			return tree[node];
		}
		else	return 0;
	}
	int mid = (start + end) / 2;
	int one = segTree(node*2 , left, right, start, mid);
	if(one > 0)	return one;
	int two = segTree(node*2+1, left, right, mid+1, end);
	if(two > 0)	return two;
	return 0;
}
int main(){
	int M, a, b;
	scanf("%d %d" , &N, &C);
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
		idx[arr[i]].push_back(i);
	}
	for(int i=1; i<=C; i++){
		sort(idx[i].begin(), idx[i].end());
	}		
	make(1, 0, N-1);
	scanf("%d", &M);
	while(M--){
		scanf("%d %d", &a, &b);
		int ans = segTree(1, a-1, b-1, 0, N-1);
		if(ans > 0)	printf("yes %d\n", ans);
		else	printf("no\n");
	}
	return 0;
}