c/c++语言开发共享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("%dn", 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 */