백준 2912 백설공주와 난쟁이

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

세그먼트 트리 설계도 어렵고 구현도 조금 까다로운 문제이다. 문제 아이디어는 다음과 같다.

문제 아이디어

  1. 절반보다 많은 수의 색을 segment tree에 저장한다. 그러한 색이 없다면 -1을 저장한다.

1-1. 어떤 구간을 2개의 구간 L,R으로 나누어 생각해보자. 그 구간에서 절반보다 많이 존재하는 색이 존재한다면, 이는 L의 절반보다 많은 색과 R의 절반보다 많은 색 중 하나이다.

1-2. lower_bound와 upper_bound를 이용하여 해당 구간에서 색의 개수를 구할 수 있다.

1-3. 1-1,1-2를 이용하여 segment tree update가 가능하다. $ log(n) \times log(n) $ 의 시간복잡도가 나온다.

  1. 구간 [l,r]에서 가장 많은 수가 있는 모자의 후보는 [l,r]의 sub range에 있는 모든 구간의 대표값들 중 하나이다.

2-1. 후보들에 대하여 모자의 개수를 모두 구해보자. 쿼리당 $ log(n) \times log(n) $ 의 시간복잡도가 나온다.

#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int,int> pii;
const int SZ=300005;
const int COL=10005;
vector<int> graph[COL];
int seg[4*SZ];
int col_num(int c, int l, int r){
	int up=upper_bound(graph[c].begin(),graph[c].end(),r)-graph[c].begin();
	int low=lower_bound(graph[c].begin(),graph[c].end(),l)-graph[c].begin();
	return up-low;
}
void update(int idx, int l, int r, int g, int d){
	if(r<g || g<l) return;
	if(l==r){
		seg[idx]=d;
		return;
	}
	update(2*idx,l,(l+r)/2,g,d);
	update(2*idx+1,(l+r)/2+1,r,g,d);
	int lc=seg[2*idx],rc=seg[2*idx+1];
	if(lc==-1 && rc!=-1){
		if(col_num(rc,l,r)>(r-l+1)/2) seg[idx]=rc;
		else seg[idx]=-1;
	}
	else if(rc==-1 && lc!=-1){
		if(col_num(lc,l,r)>(r-l+1)/2) seg[idx]=lc;
		else seg[idx]=-1;		
	}
	else if(lc!=-1 && rc!=-1){
		if(col_num(rc,l,r)>(r-l+1)/2) seg[idx]=rc;
		else if(col_num(lc,l,r)>(r-l+1)/2) seg[idx]=lc;
		else seg[idx]=-1;
	}
	else seg[idx]=-1;
}
int find(int idx, int l, int r, int fl, int fr){
	if(r<fl || fr<l) return -1;
	if(fl<=l && r<=fr) return seg[idx];
	int lc=find(2*idx,l,(l+r)/2,fl,fr);
	int rc=find(2*idx+1,(l+r)/2+1,r,fl,fr);
	if(lc==-1 && rc!=-1){
		if(col_num(rc,fl,fr)>(fr-fl+1)/2) return rc;
		return -1;
	}
	else if(rc==-1 && lc!=-1){
		if(col_num(lc,fl,fr)>(fr-fl+1)/2)  return lc;
		return -1;		
	}
	else if(lc!=-1 && rc!=-1){
		if(col_num(rc,fl,fr)>(fr-fl+1)/2) return rc;
		if(col_num(lc,fl,fr)>(fr-fl+1)/2) return lc;
		return -1;
	}
	return -1;		
}
int main(void){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	memset(seg,-1,sizeof(seg));
	int n,c; cin>>n>>c;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		graph[x].pb(i);
		update(1,1,n,i,x);
	}
	int q; cin>>q;
	while(q--){
		int l,r; cin>>l>>r;
		int ans=find(1,1,n,l,r);
		if(ans==-1) cout<<"no"<<'\n';
		else cout<<"yes "<<ans<<'\n';
	}
	return 0;
}