bzoj2223 [Coci 2009]PATULJCI

Description

考虑到n很大，m较小，可以用归并树，建树和预处理区间答案O(nlogn)

一个数在区间内出现次数过半，则至少在某一个子区间内出现次数过半，

对每次询问查出子区间中出现次数过半的数并检查其在总区间的出现次数，单次询问复杂度为O(log³n)

#include<cstdio>
#include<algorithm>
int n,mxv,m;
inline int input(){
    int x=0,c=getchar();
    while(c>57||c<48)c=getchar();
    while(c>47&&c<58)x=x*10+c-48,c=getchar();
    return x;
}
int l,r;
int xs[300005];
int tr[20][300005],mx[20][300005];
void build(int h,int L,int R){
    if(L==R){
        mx[h][L]=tr[h][L]=xs[L];
        return;
    }
    int M=L+R>>1;
    build(h+1,L,M);
    build(h+1,M+1,R);
    int*p1=tr[h+1]+L,*p2=tr[h+1]+M+1,*p3=tr[h]+L;
    int*r1=tr[h+1]+M+1,*r2=tr[h+1]+R+1;
    while(p1!=r1&&p2!=r2)*(p3++)=(*p1<*p2?*(p1++):*(p2++));
    while(p1!=r1)*(p3++)=*(p1++);
    while(p2!=r2)*(p3++)=*(p2++);
    int*a=tr[h],v=-1,mv=-1,mt=0,t=0;
    for(int i=L;i<=R;i++){
        if(v!=a[i])t=0,v=a[i];
        ++t;
        if(t>mt)mt=t,mv=v;
    }
    if(mt*2>R-L+1)mx[h][L]=mv;
}
int ms[64],mp,ans;
void find(int h,int L,int R){
    if(l<=L&&R<=r){
        if(mx[h][L])ms[mp++]=mx[h][L];
        return;
    }
    int M=L+R>>1;
    if(l<=M)find(h+1,L,M);
    if(r>M)find(h+1,M+1,R);
}
void chk(int x,int h,int L,int R){
    if(l<=L&&R<=r){
        ans+=std::upper_bound(tr[h]+L,tr[h]+R+1,x)-std::lower_bound(tr[h]+L,tr[h]+R+1,x);
        return;
    }
    int M=L+R>>1;
    if(l<=M)chk(x,h+1,L,M);
    if(r>M)chk(x,h+1,M+1,R);
}
int main(){
    n=input();mxv=input();
    for(int i=0;i<n;i++)xs[i]=input();
    build(0,0,n-1);
    m=input();
    while(m--){
        l=input()-1,r=input()-1;mp=0;
        find(0,0,n-1);
        for(int i=0;i<mp;i++){
            ans=0;
            chk(ms[i],0,0,n-1);
            if(ans*2>r-l+1){
                printf("yes %d
",ms[i]);
                goto end;
            }
        }
        puts("no");
        end:;
    }
    return 0;
}