# bzoj 3524 [Poi2014]Couriers

### Description

m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

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

7 5

1 1 3 2 3 4 3

1 3

1 4

3 7

1 7

6 6

1

0

3

0

4

【数据范围】

n,m≤500000

### 题解

#include <cstdio>
using namespace std;
const int N = 500010;
struct data {
int sum, l, r;
}pri[N * 20];
int n, m, root[N], x, y, z, tot;
void inserts(int pos, int &now, int l, int r) {
pri[++tot] = pri[now], now = tot, pri[now].sum++;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) inserts(pos, pri[now].l, l, mid);
else inserts(pos, pri[now].r, mid + 1, r);
}
int query(int l, int r, int x, int y, int z) {
if (l == r) return l;
int mid = l + r >> 1;
if (pri[pri[y].l].sum - pri[pri[x].l].sum > z)
return query(l, mid, pri[x].l, pri[y].l, z);
if (pri[pri[y].r].sum - pri[pri[x].r].sum > z)
return query(mid + 1, r, pri[x].r, pri[y].r, z);
return 0;
}
main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
root[i] = root[i - 1],
scanf("%d", &x), inserts(x, root[i], 1, n);
for (int i = 1; i <= m; ++i)
scanf("%d%d", &x, &y),
printf("%d\n", query(1, n, root[x - 1], root[y], (y - x + 1) / 2));
}


#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 500010;
vector <int> pos[N];
int a[N], l, r, n, m;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) pos[i].clear();
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]), pos[a[i]].push_back(i);
while(m--) {
scanf("%d%d", &l, &r);
int len = r - l + 1, find = 0;
for(int k = 1; k <= 20; k++) {
int u = a[l + rand() % len];
int st = lower_bound(pos[u].begin(), pos[u].end(), l) - pos[u].begin();
int en = upper_bound(pos[u].begin(), pos[u].end(), r) - pos[u].begin();
if((en - st) * 2 > len) {
find = u;
break;
}
}
if(find) printf("%d\n", find);
else puts("0");
}
}