[BOJ] 2912번: PATULICI

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

세그먼트 트리에서 구간을 나누는 것과 같이 구간을 나눕니다. 이제 각 구간에는 해당하는 구간에서 절반을 초과한 색깔을 저장합니다. 이는 맨 처음 색을 다 입력받은 후 재귀적으로 트리를 만드는 방법으로 저장할 수 있습니다. 주어진 쿼리에 해당하는 구간을 세그먼트 트리대로 쪼개고 나면, 반드시 어느 한 구간에서는 정답인 색깔이 가장 많이 등장해야 합니다. 그러므로 각 쿼리에 대해 최대 $lg N$개의 색에 대해 확인을 하면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/2912.cpp