欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[bzoj3524][Couriers]

程序员文章站 2022-11-21 10:11:59
题目链接 思路 观察这个$(r - l + 1)/2$,很容易证明,如果一个数出现次数大于$(r - l + 1) / 2$,那么这个区间内第$(r - l + 1) / 2 + 1$ ......

题目链接

思路

观察这个\((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;
}