BZOJ 3524: [Poi2014]Couriers

正文索引 [隐藏]

Description

给一个长度为n的序列a。1≤a[i]≤n。
m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。

Input

第一行两个数n,m。
第二行n个数,a[i]。
接下来m行,每行两个数l,r,表示询问[l,r]这个区间。

Output

m行,每行对应一个答案。

Sample Input

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6

Sample Output

1
3
4

HINT

【数据范围】
n,m≤500000

题解

这题就是可持久化线段树辣!把同构的两颗线段树做差就可以计算区间问题了!
我觉得难点在空间、、我一开始记录了左右区间,要么编译爆掉,要么Re、、
后来就写了个不记录左右区间的,才过、、这真是、、、可怕、、

双倍经验 => BZOJ 2223