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
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
1
0
3
0
4
0
3
0
4
HINT
【数据范围】
n,m≤500000
题解
挺裸的主席树吧。。。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype> #define mid (l + r >> 1) inline void read(int & x)
{
x = ;
int k = ;
char c = getchar();
while (!isdigit(c))
if (c == '-') c = getchar(), k = -;
else c = getchar();
while (isdigit(c))
x = (x << ) + (x << ) + (c ^ ),
c = getchar();
x *= k;
} const int N = ; int n, m, id, cnt, x, y;
int root[N], a[N], b[N], L[N], R[N], val[N]; inline int Lsh(int x)
{
return std::lower_bound(a + , a + cnt + , x) - a;
} inline void Pushup(int u)
{
val[u] = val[L[u]] + val[R[u]];
} int Build(int u, int l, int r)
{
if (l == r)
{
L[u] = R[u] = ;
val[u] = ;
return u;
}
L[u] = Build(++id, l, mid);
R[u] = Build(++id, mid + , r);
Pushup(u);
return u;
} int Add(int u, int l, int r, int x)
{
int cur = ++id;
L[cur] = L[u],
R[cur] = R[u],
val[cur] = val[u] + ;
if (l < r)
if (x <= mid) L[cur] = Add(L[u], l, mid, x);
else R[cur] = Add(R[u], mid + , r, x);
return cur;
} int Query(int u, int v, int l, int r, int Std)
{
if (l == r) return l;
if (val[L[v]] - val[L[u]] > Std)
return Query(L[u], L[v], l, mid, Std);
if (val[R[v]] - val[R[u]] > Std)
return Query(R[u], R[v], mid + , r, Std);
return ;
} int main()
{
read(n), read(m);
for (int i = ; i <= n; ++i)
read(b[i]), a[i] = b[i];
std::sort(a + , a + n + );
cnt = std::unique(a + , a + n + ) - a - ;
root[] = Build(++id, , cnt);
for (int i = ; i <= n; ++i)
root[i] = Add(root[i - ], , cnt, Lsh(b[i]));
for (int i = ; i <= m; ++i)
read(x), read(y),
printf("%d\n", Query(root[x - ], root[y], , cnt, (val[root[y]] - val[root[x - ]] >> )));
return ;
}