F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5178. -- [Jsoi2011]棒棒糖

5178: [Jsoi2011]棒棒糖

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 163  Solved: 90
[Submit][Status][Discuss]

Description

Coffee的世界里也是有棒棒糖卖的,Coffee买了N(1≤N≤50000)只连着的。这N只棒棒糖包裹在小塑料袋中,排成
一列,相邻的两只棒棒糖的塑料袋是接起来的。为了方便,我们把棒棒糖从左到右编号为1..N。每只棒棒糖有一种
口味。第i只的口味是ci(1≤ci≤50000)。两只棒棒糖i,j的口味相同,当且仅当ci=cj。Coffee对m只棒棒糖总体口
味的评价比较奇怪。如果这m只棒棒糖中,有一种口味c0的数量严格大于总数的一半m/2,那么Coffee认为这m只棒
棒糖主要是c0口味的。Coffee知道,这里的c0如果存在就一定是唯一的。而当c0不存在时,Coffee认为这m只棒棒
糖是混合口味的。Coffee暂时舍不得吃棒棒糖,它在想一些好玩的问题。如果考虑棒棒糖序列的一个连续子序列s.
.t(1≤s≤t≤N),包括棒棒糖s和t。那么这t-s+1只棒棒糖的总体口味是什么呢?
Coffee有一堆这样的问题,一共M(1≤M≤50000)个。
第i个问题是棒棒糖子序列si..ti的总体口味。请你帮忙解决。

Input

第1行:两个用空格隔开的整数,分别表示N,M。
第2..N+1行:每行一个整数,第i+1行表示ci。
第N+2..N+M+1行:每行两个用空格隔开的整数
第i+N+1行表示,si,ti。

Output

第1..M行:每行一个整数
第i个整数表示你对第i个问题的回答,也就是si..ti的总体口味。
如果总体口味是c0,那么回答用c0表示。
如果总体口味是混合口味,那么回答用0表示

Sample Input

5 3
1
2
2
1
1
1 5
2 5
2 4

Sample Output

1
0
2
棒棒糖1..5中,口味1的棒棒糖有3只,一共5只棒棒糖,而3>5/2=2.5,所以主要口味为1。棒棒糖2..5中,一共4只
棒棒糖,没有一种口味的棒棒糖个数严格大于4/2=2,所以是混合口味的。棒棒糖2..4中,一共3只棒棒糖,口味2
的棒棒糖有2只,2>3/2=1.5,主要口味为2。

HINT

Source

[Submit][Status][Discuss]

HOME Back