bzoj 3524 [Poi2014]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

题解

这题是主席树裸题。。

#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");
    }
}