BOJ 2912 - 백설공주와 난쟁이 (머지소트트리, 구간 과반수)

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

한 구간의 원소중 무작위로 하나 골랐을 때 그 원소가 그 구간의 과반수일 확률은 (1/2) 이상이다.

 

이를 이용해서, 한 쿼리당 20번씩 무작위로 골라서 확률을 높이는 방법도 존재한다.

~~(1e6-1)/1e6의 쿼리개수 승 = 99.00++%

 

<문제설명>

최대 길이 3e5의 배열이 주어진다. 모자 색의 가짓수는 1e4 이하이다. 다음 쿼리를 처리하자

 

s, e : 구간[s,e]의 과반수값이 존재하면 "yes 과반수값", 존재하지 않으면 "no" 출력

 

<풀이>

vector c[i] : i색상 모자를 갖는 인덱스들 (오름차순)

 

구간[s,e] 사이에 i색상 모자가 몇 개 들어있는지는 위 벡터에서 이분탐색하여 알 수 있다.

 

 

머지소트트리 상에서 해당 구간에 포함되는 블럭들을 모두 생각해보면, 최대 logn개의 블럭이 있다.

(각 블럭의 크기는 2의 거듭제곱 꼴이다)

 

각 블럭에서 과반수값이 될 수 있는 후보 값들을 하나씩 뽑는다면 최대 logn개이다.

 

만약 구간 과반수값이 존재한다면 그 값은 어떤 블럭에서의 과반수값일 것이다.

 

각 블럭의 크기가 2*k라면 k번째, k+1번째 값이 같은 경우 그 값이 과반수 값이 될 가능성이 있다.

 

모든 후보값들에 대해 구간 과반수값인지 확인해주면 된다.

 

<코드>

const int MAX = 3e5 + 4;
const int SMAX = (1 << 20);

int n, qq;
vector<int> seg[SMAX], c[10001];
vector<int> temp;

void construct() {
	for (int i = SMAX / 2 - 1; i >= 1; i--) {
		seg[i] = seg[i * 2 + 1];
		seg[i].insert(seg[i].end(), seg[i * 2].begin(), seg[i * 2].end());
		sort(seg[i].begin(), seg[i].end());
	}
}

void val(int s, int e, int i=1, int ns=0, int ne=SMAX/2-1) {
	if (e < ns || ne < s) return;
	if (s <= ns && ne <= e) {
		int k = (ne - ns + 1) / 2 - 1;
		if (ns == ne) temp.push_back(seg[i][0]);
		else if (seg[i][k] == seg[i][k + 1]) temp.push_back(seg[i][k]);
		return;
	}
	int md = (ns + ne) / 2;
	val(s, e, i * 2, ns, md);
	val(s, e, i * 2 + 1, md + 1, ne);
}

int main() {
	FAST; cin >> n >> qq;
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		c[x].push_back(i);
		seg[i + SMAX / 2].push_back(x);
	}
	construct();
	cin >> qq;
	for (int i = 0, s, e; i < qq; i++) {
		cin >> s >> e;
		val(s, e);

		bool flag = false;
		for (int j : temp) {
			int t = upper_bound(c[j].begin(), c[j].end(), e) - lower_bound(c[j].begin(), c[j].end(), s);
			if (t > (e - s + 1) / 2) {
				flag = true;
				cout << "yes " << j << '\n';
				break;
			}
		}

		if (!flag) cout << "no\n";
		temp.clear();
	}
}

 

<생각>

머지소트트리의 일반적인 활용은 아니다. 애초에 문제 자체가 일반적인 풀이로 해결하기 쉽지 않아보인다. 평방분할하여 푸는 방법이 가장 많이 쓰이는 것 같다.