[bzoj3524][Couriers]

題目鏈接

思路

觀察這個\((r - l + 1)/2\)，很容易證明，如果一個數出現次數大於\((r - l + 1) / 2\)，那麼這個區間內第\((r - l + 1) / 2 + 1\)大一定是這個數。所以只要用主席樹查詢出區間內第\((r - l + 1) / 2 + 1\)大,然後再去查這個數在這個區間內出現次數，就行了。

代碼

/*
* @Author: wxyww
* @Date:   2018-12-11 16:59:21
* @Last Modified time: 2018-12-11 17:12:03
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 500000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    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 tree[N * 30],ls[N * 30],rs[N * 30];
int a[N],root[N],tot;
void update(int &rt,int lst,int l,int r,int pos) {
    rt = ++tot;
    ls[rt] = ls[lst];rs[rt] = rs[lst];
    tree[rt] = tree[lst] + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ls[rt],ls[lst],l,mid,pos);
    else update(rs[rt],rs[lst],mid + 1,r,pos);
}
int kth(int L,int R,int l,int r,int k) {
    int z = tree[ls[R]] - tree[ls[L]];
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(k <= z) return kth(ls[L],ls[R],l,mid,k);
    else return kth(rs[L],rs[R],mid + 1,r,k - z);
}
int query(int rt,int l,int r,int pos) {
    if(l == r) return tree[rt];
    int mid = (l + r) >> 1;
    if(pos <= mid) return query(ls[rt],l,mid,pos);
    else return query(rs[rt],mid + 1,r,pos);
}
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;++i) update(root[i],root[i - 1],1,n,read());

    while(m--) {
        int l = read(),r = read();
        int k = kth(root[l - 1],root[r],1,n,(r - l + 1) / 2 + 1);
        int z = query(root[r],1,n,k) - query(root[l - 1],1,n,k);
        if(z > (r - l + 1) / 2) printf("%d\n",k);
        else puts("0");
    }
    return 0;
}