BOJ 2912(백설공주와 난쟁이)풀이

solved.ac 티어 : 플래 3

www.acmicpc.net/problem/2912

2912번: 백설공주와 난쟁이

이문제는 수열과 쿼리 6을 응용하면 된다.

6 코드에서 값을 재일 마지막에 구해주면 된다.

처음에는 안될 줄 알았는데 이렇게 해줘도 시간이 여유롭게 남는다.

void add(int u){
    cn[cnt[u]]--;
    cn[cnt[u]+1]++;
}
void ms(int u){
    cn[cnt[u]]--;
    cn[cnt[u]-1]++;
}

fcnt=0;
value=0;
while(Qur[i].s < s){s--;add(L[s]);cnt[L[s]]++;}
while(e < Qur[i].e){add(L[e]);cnt[L[e]]++;e++;}
while(Qur[i].s > s){ms(L[s]);cnt[L[s]]--;s++;}
while(e > Qur[i].e){e--;ms(L[e]);cnt[L[e]]--;}
for(int j=1;j<=QT;j++){
	if(fcnt<cnt[j]){fcnt=cnt[j];value=j;}
}
ans[Qur[i].n] = {fcnt,value};

수쿼 6 코드를 이 부분만 수정해주면 된다.