3524: [Poi2014]Couriers
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 2895 Solved: 1189
[Submit][Status][Discuss]
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
題解
挺裸的主席樹吧。。。
1 #include <algorithm>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cstdio>
6 #include <cctype>
7
8 #define mid (l + r >> 1)
9
10 inline void read(int & x)
11 {
12 x = 0;
13 int k = 1;
14 char c = getchar();
15 while (!isdigit(c))
16 if (c == '-') c = getchar(), k = -1;
17 else c = getchar();
18 while (isdigit(c))
19 x = (x << 1) + (x << 3) + (c ^ 48),
20 c = getchar();
21 x *= k;
22 }
23
24 const int N = 10050500;
25
26 int n, m, id, cnt, x, y;
27 int root[N], a[N], b[N], L[N], R[N], val[N];
28
29 inline int Lsh(int x)
30 {
31 return std::lower_bound(a + 1, a + cnt + 1, x) - a;
32 }
33
34 inline void Pushup(int u)
35 {
36 val[u] = val[L[u]] + val[R[u]];
37 }
38
39 int Build(int u, int l, int r)
40 {
41 if (l == r)
42 {
43 L[u] = R[u] = 0;
44 val[u] = 0;
45 return u;
46 }
47 L[u] = Build(++id, l, mid);
48 R[u] = Build(++id, mid + 1, r);
49 Pushup(u);
50 return u;
51 }
52
53 int Add(int u, int l, int r, int x)
54 {
55 int cur = ++id;
56 L[cur] = L[u],
57 R[cur] = R[u],
58 val[cur] = val[u] + 1;
59 if (l < r)
60 if (x <= mid) L[cur] = Add(L[u], l, mid, x);
61 else R[cur] = Add(R[u], mid + 1, r, x);
62 return cur;
63 }
64
65 int Query(int u, int v, int l, int r, int Std)
66 {
67 if (l == r) return l;
68 if (val[L[v]] - val[L[u]] > Std)
69 return Query(L[u], L[v], l, mid, Std);
70 if (val[R[v]] - val[R[u]] > Std)
71 return Query(R[u], R[v], mid + 1, r, Std);
72 return 0;
73 }
74
75 int main()
76 {
77 read(n), read(m);
78 for (int i = 1; i <= n; ++i)
79 read(b[i]), a[i] = b[i];
80 std::sort(a + 1, a + n + 1);
81 cnt = std::unique(a + 1, a + n + 1) - a - 1;
82 root[0] = Build(++id, 1, cnt);
83 for (int i = 1; i <= n; ++i)
84 root[i] = Add(root[i - 1], 1, cnt, Lsh(b[i]));
85 for (int i = 1; i <= m; ++i)
86 read(x), read(y),
87 printf("%d\n", Query(root[x - 1], root[y], 1, cnt, (val[root[y]] - val[root[x - 1]] >> 1)));
88 return 0;
89 }