【BZOJ3524】Couriers


题面

Description

给一个长度为\(n\)的序列\(a\)。\(1\le a[i]\le 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
0
3
0
4

HINT

\(n,m\le 500000\)


分析

主席树维护权值线段树,直接在树上二分。

 

You may also like

LEAVE A COMMENT

Statistics

  • 1
  • 2,003

Categories

Archive