[BOJ 2912]백설공주와 난쟁이

[BOJ 2912]백설공주와 난쟁이 - P3

문제 설명

난쟁이가 n명 주어진다. 난쟁이는 각자 하나의 숫자를 갖고 있다. 이어서 쿼리가 주어진다. 각 쿼리는 [l,r]형태로 주어지는데, [l,r] 구간 안에서 난쟁이가 갖고 있는 특정 숫자의 개수가 구간의 길이(r-l+1)의 절반을 초과하는지 묻고 있다.

문제 풀이

특정 숫자의 개수가 구간 길이의 절반을 초과한다면, '반드시' 구간의 절반 경계를 지날 때, 등장하는 수가 같아야만 한다. 단, 역은 성립하지 않는다. 즉 절반의 경계에서 등장하는 수가 같더라도 그 수의 개수가 절반을 초과하지 않을 수도 있다. 따라서 그냥 정답의 '후보'만 된다는 것이고 이는 나중에 실제로 정답인지 검증하는 과정을 거쳐야 한다. 이러한 '후보'는 최대 logL 개가 나온다.(L = r-l+1)
따라서 모든 후보를 구해놓고 각 후보마다 실제로 개수가 절반이 넘는지 검증해보면 된다. 검증할 때는 전처리로 각 숫자가 등장하는 인덱스를 벡터에 넣어놓고 [l,r]구간에 몇개가 등장하는지 이분 탐색을 돌려보면 된다.

소스 코드

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

const int SIZE = 300009;
vector<int> tree[SIZE*8],color[10009];
int startIdx=1;

void makeMergeSortTree(){
    for(int i = startIdx - 1; i>=1 ; i--){
        int lChild = i*2,rChild = i*2+1;
        int lIdx = 0,rIdx = 0;
        int sz = tree[lChild].size();

        while(lIdx < tree[lChild].size() && rIdx < tree[rChild].size()){
            if(tree[lChild][lIdx] > tree[rChild][rIdx]) tree[i].push_back(tree[rChild][rIdx++]);
            else tree[i].push_back(tree[lChild][lIdx++]);
        }

        if(lIdx < tree[lChild].size()){
            for(int j = lIdx ; j < tree[lChild].size() ; j++){
                tree[i].push_back(tree[lChild][j]);
            }
        }
        else for(int j = rIdx ; j < tree[rChild].size() ; j++){
            tree[i].push_back(tree[rChild][j]);
        }
    }

}

vector<int> query(int node,int cl, int cr,int ql,int qr){
    vector<int> res;
    if(tree[node].size()==0) return res;
    int mid = (cl+cr)/2;
    int sz = cr - cl +1;
    if(node >= startIdx) {
        res.push_back(tree[node][0]);
        return res;
    }
    if(cl > qr || ql > cr) return res;
    if(qr >= cr && cl >= ql) {
        if(tree[node][sz/2-1] == tree[node][sz/2]) {
            res.push_back(tree[node][sz/2]);
        }
        return res;
    }

    res = query(node*2,cl,mid,ql,qr);
    vector<int> R = query(node*2+1,mid+1,cr,ql,qr);
    for(int i : R)
        res.push_back(i);

    return res;
}

int countColor(int l,int r,int i){
    int res = upper_bound(color[i].begin(),color[i].end(),r) - 
        upper_bound(color[i].begin(),color[i].end(),l-1);

    return res;
}

int main(){
    int n,c;    scanf("%d %d",&n,&c);
    for(;startIdx < n ; startIdx *= 2);

    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
        tree[startIdx + i - 1].push_back(inp);
        color[inp].push_back(i);
    }

    makeMergeSortTree();

    int q;  scanf("%d",&q);
    while(q--){
        int l,r;    scanf("%d %d",&l,&r);
        vector<int> candid = query(1,1,startIdx,l,r);

        int check = 0;
        for(int i : candid){
            if(countColor(l,r,i) > (r-l+1)/2){
                printf("yes %d",i);
                check = 1;
                break;
            }
        }

        if(!check) printf("no");
        printf("\n");
    }
    return 0;
}