【BZOJ 3524】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
0
3
0
4

HINT

【数据范围】

n,m≤500000

分析：

　　主席树直接做，查询时候其实比平常的主席树更容易。

　　有一个问题就是没给出a[i]的范围真的好吗。。。就也当作500000吧。。

代码：

 1 #include <cstdio>
 2 
 3 const int maxn = 500010;
 4 
 5 int n, m, num[maxn], root[maxn];
 6 int ch[maxn * 20][2], size[maxn * 20], s;
 7 int aski, askj, key;
 8 
 9 #define MID (left + right >> 1)
10 
11 int insert (int left, int right, int last)
12 {
13     int i = ++s, d = key > MID;
14     size[i] = size[last] + 1;
15     if (left != right)
16     {
17         ch[i][!d] = ch[last][!d];
18         d ? left = MID + 1 : right = MID;
19         ch[i][d] = insert (left, right, ch[last][d]);
20     }
21     return i;
22 }
23 
24 #define SIZE(a) (size[ch[f2][a]] - size[ch[f1][a]])
25 
26 int query (int left, int right, int f1, int f2)
27 {
28     if (left == right) return left;
29     if (SIZE (0) > key) return query (left, MID, ch[f1][0], ch[f2][0]);
30     else if (SIZE (1) > key) return query (MID + 1, right, ch[f1][1], ch[f2][1]);
31     return 0;
32 }
33 
34 int main ()
35 {
36     scanf ("%d %d", &n, &m);
37     root[0] = s = 0;
38     for (int i = 1; i <= n; i++)
39     {
40         scanf ("%d", &num[i]);
41         key = num[i];
42         root[i] = insert (1, n, root[i - 1]);
43     }
44     for (int i = 0; i < m; i++)
45     {
46         scanf ("%d %d", &aski, &askj);
47         key = askj - aski + 1 >> 1;
48         printf ("%d
", query (1, n, root[aski - 1], root[askj]));
49     }
50 }