这道题有了主席树，就是裸题了……

只要用主席树维护出现次数，然后二分求解即可

但是！数组一定要开大，开大，再开大，重要的事情说三遍！

代码：

/**************************************************************
    Problem: 3524
    User: danihao123
    Language: C++
    Result: Accepted
    Time:6432 ms
    Memory:129712 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001,maxnode=maxn*21;
int sumv[maxnode];
int lc[maxnode];
int rc[maxnode];
int root[maxn];
int A[maxn],A2[maxn];
int size,cnt=0;
int build_tree(int L,int R){
    int ans=++cnt;
    if(L==R)
        return ans;
    int M=L+(R-L)/2;
    lc[ans]=build_tree(L,M);
    rc[ans]=build_tree(M+1,R);
    return ans;
}
int p;
int update(int o,int L,int R){
    int roo=++cnt;
    sumv[roo]=sumv[o];
    lc[roo]=lc[o];
    rc[roo]=rc[o];
    if(R>L){
        int M=L+(R-L)/2;
        if(p<=M)
            lc[roo]=update(lc[roo],L,M);
        else
            rc[roo]=update(rc[roo],M+1,R);
    }
    sumv[roo]++;
    return roo;
}
int ql,qr;
int query(int lo,int ro,int L,int R){
    if(L==R){
        return A2[L-1];
    }
    int M=L+(R-L)/2,lc_siz=sumv[lc[ro]]-sumv[lc[lo]],rc_siz=sumv[rc[ro]]-sumv[rc[lo]];
    if(lc_siz>((qr-ql+1)/2))
        return query(lc[lo],lc[ro],L,M);
    if(rc_siz>((qr-ql+1)/2))
        return query(rc[lo],rc[ro],M+1,R);
    return 0;
}
void init_tree(int n){
    sort(A2,A2+n);
    size=unique(A2,A2+n)-A2;
    root[0]=build_tree(1,size);
    for(register int i=1;i<=n;i++){
        p=lower_bound(A2,A2+size,A[i-1])-A2+1;
        root[i]=update(root[i-1],1,size);
    }
}
int main(){
    int n,m;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
        A2[i]=A[i];
    }
    init_tree(n);
    for(i=0;i<m;i++){
        scanf("%d%d",&ql,&qr);
        printf("%d\n",query(root[ql-1],root[qr],1,size));
    }
    return 0;
}

• 相关文章
• 全局相关文章