PATULJCI  Snow White and the N dwarfs
Snow White and the N dwarfs live in the forest. While the dwarfs mine away Snow White hangs around social networks.
Each morning the dwarfs form a long line and go whistling away to the mine. Snow White runs around them and snaps pictures to upload onto her favorite social network.
When dwarfs enter the mine, Snow White goes back to their house and goes through the pictures, selecting pretty ones. Each dwarf has a colored cap, and there are C different colors. A picture is pretty if more than half caps on it are of the same color. In other words, if there are K dwarfs on the picture, it is pretty if strictly more than K / 2 dwarfs have same colored caps.
Write a program that will check for a set of M pictures if they are pretty, and what color is dominating if they are.
Input
First line contains two integers N and C (3 ≤ N ≤ 300000, 1 ≤ C ≤ 100000) number of dwarfs and number of colors.
Second line contains N integers between 1 and C (inclusive), colors of dwarves hats, ordered the way they formed the line that morning.
Third line contains M (1 ≤ M ≤ 100000), number of pictures.
Next M lines contain two integers A and B (1 ≤ A ≤ B ≤ N). Each line describes one picture. On it there are all dwarves starting from Ath all the way to the Bth.
Output
Output M lines. For each picture output “no” if Snow White doesn't think the picture is pretty, and “yes X”, where X is the color dominating on the picture, if she does.
Example
Input: 10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10 Output: no yes 1 no yes 1 no yes 2 no yes 3
hide comments
nh0902:
20240720 08:43:41
Answer yourself this question: if you already know the "dominating" color of two interval, what is the "domniating" color of the combining interval ?


kesh4281:
20200402 06:59:03
this can be done with randomised algorithms as well!! 

Sigma Kappa:
20180612 14:00:44
Is not the complexity O((N+M)sqrt(N)log(C))? How did you guys get rid of the log(C)? We need to maintain the frequency of each number, right? Hence log(C) 

gustavonunes:
20180309 13:53:47
O((N +M)*sqrt) passes. I did use block of size 333 and worked nice 

tiaguito80:
20171204 18:29:32
SQRT Decomposition won't pass, there is a nice solution which works in (n*log(n))/(ratio) where ratio is 1/2 in this problem.. 

Ashwani Gautam:
20170318 14:41:33
will O((N+M) * root(N)) pass ? mine doesn't :( 

spoj2121:
20160329 20:35:18
learned something new... 

Bryan Poulsen:
20160223 22:58:24
I am going to guess this unsolvable in python with the give time limit. 

Raghav Dilip Mundhada:
20151103 20:22:20
think out of box :)


Raghav Dilip Mundhada:
20151103 20:21:54
nice problem on suffix tree ....... enjoyed solving this Q!!! 
Added by:  Luka Kalinovcic 
Date:  20091221 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  COCI 2009/2010 Contest #3 