[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;
}