P3567 [POI2014]KUR-Couriers

思路

区间内x出现次数大于一半
区间内排序，则x一定会在(一半+1)的位置上出现
找到那个数，再检查一下就好

错误

快读写错了、、，又浪费了1h

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=5e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>='9'||s<='0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,a[maxn],b[maxn];
struct node {
    int ch[2],siz;
}e[maxn*30];
int rt[maxn],cnt;
void build(int &now,int old,int l,int r,int k) {//build
    now=++cnt;
    e[now]=e[old];
    e[now].siz++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) build(e[now].ch[0],e[old].ch[0],l,mid,k);
    else build(e[now].ch[1],e[old].ch[1],mid+1,r,k); 
}
int query_1(int now,int old,int l,int r,int k) {//[l,r] k_th
    if(l==r) return l;
    int tot=e[e[now].ch[0]].siz-e[e[old].ch[0]].siz,mid=(l+r)>>1;
    if(tot>=k) 
        return query_1(e[now].ch[0],e[old].ch[0],l,mid,k);
    else
        return query_1(e[now].ch[1],e[old].ch[1],mid+1,r,k-tot);
}
int query_2(int now,int old,int l,int r,int k) { //[l,r] how many k
    if(l==r) return e[now].siz-e[old].siz;
    int mid=(l+r)>>1;
    if(k<=mid)  return query_2(e[now].ch[0],e[old].ch[0],l,mid,k);
    else return query_2(e[now].ch[1],e[old].ch[1],mid+1,r,k);
} 
int main() {
    //read and lsh
    n=read(),m=read();
    FOR(i,1,n)
        a[i]=b[i]=read();
    sort(b+1,b+1+n);
    int len=unique(b+1,b+1+n)-b-1;
    FOR(i,1,n)
        a[i]=lower_bound(b+1,b+1+len,a[i])-b;
    // init
    FOR(i,1,n)
        build(rt[i],rt[i-1],1,len,a[i]);
    // work
    FOR(i,1,m) {
        int x=read(),y=read(),k=(y-x+1)/2+1;
        int ans=query_1(rt[y],rt[x-1],1,len,k);
        int check=query_2(rt[y],rt[x-1],1,len,ans);
        if(check>=k) cout<<b[ans]<<"
";
        else cout<<"0
"; 
    }
    return 0;
}