BZOJ3524: [Poi2014]Couriers(主席树)

题意

题目链接

sol

严格众数只会出现一次，那么建出主席树，维护子树siz，直接在树上二分即可

#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int maxn = 2e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, a[maxn], date[maxn], rt[maxn], num;
//struct gzyakioi {
#define max (maxn * 10)
    int tot, ls[max], rs[max], siz[max];
    void insert(int &rt, int pre, int l, int r, int v) {
        rt = ++tot; ls[rt] = ls[pre]; rs[rt] = rs[pre]; siz[rt] = siz[pre] + 1;
        if(l == r) return ;
        int mid = l + r >> 1;
        if(v <= mid) insert(ls[rt], ls[pre], l, mid, v);
        else insert(rs[rt], rs[pre], mid + 1, r, v);
    }
    int query(int pre, int rt, int l, int r, int v) {
        if(l == r) return (siz[rt] - siz[pre] > v ? date[l] : 0);  
        int mid = l + r >> 1;
        if(siz[ls[rt]] - siz[ls[pre]] > v) return query(ls[pre], ls[rt], l, mid, v);
        else return query(rs[pre], rs[rt], mid + 1, r, v);
    }
//}t;

signed main() {
    n = read(); m = read();
    for(int i = 1; i <= n; i++) a[i] = date[i] = read();
    sort(date + 1, date + n + 1);
    num = unique(date + 1, date + n + 1) - date - 1;
    for(int i = 1; i <= n; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date, insert(rt[i], rt[i - 1], 1, num, a[i]); 
    while(m--) {
        int l = read(), r = read();
        printf("%d\n", query(rt[l - 1], rt[r], 1, num, (r - l + 1) / 2));
    }
    return 0;
}
/*
7 5
1 1 3 2 3 4 3
6 6
1 3
1 4
3 7
1 7
*/