HDU-6278 Just h-index（2018湘潭邀请赛 C题---主席树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6278

题目大意：给n个数，q次询问，每次询问给出一个区间[l,r]，要你求出最大的h，使得在[l,r]这个区间内满足，有h个数的值大于等于h。

题目思路：因为数据范围是1e5，如果使用暴力求解肯定是不行的，这时就要借助一个数据结构主席树。因为我们是要求出区间中是否有h个数大于等于h，那么我们可以将思路逆转过来，如果我们可以借助主席树求出区间第 k 大的值是多少（假设为 x），那么这个区间中就有len-k+1个数是大于等于x的（len为区间长度），这样通过二分h，每次判断区间中是否有 h 个数大于 h 即可。具体实现看代码：

#include <bits/stdc++.h>
using namespace std;
const int MX=1e5+7;

int n,q,tot;
int root[MX],a[MX];
int ls[MX*40],rs[MX*40],sum[MX*40];
vector<int>v;
int get_id(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void build(int l,int r,int &rt){
    rt=++tot;sum[rt]=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,ls[rt]);
    build(mid+1,r,rs[rt]);
}
void update(int l,int r,int &rt,int pre,int pos){
    rt=++tot;ls[rt]=ls[pre];rs[rt]=rs[pre];sum[rt]=sum[pre]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(mid>=pos) update(l,mid,ls[rt],ls[pre],pos);
    else update(mid+1,r,rs[rt],rs[pre],pos);
}
int query(int l,int r,int rt,int pre,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    int cnt=sum[ls[pre]]-sum[ls[rt]];
    if(cnt>=k) return query(l,mid,ls[rt],ls[pre],k);
    return query(mid+1,r,rs[rt],rs[pre],k-cnt);
}

int main(){
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&q)){
        tot=0;v.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        build(1,n,root[0]);
        for(int i=1;i<=n;i++) update(1,n,root[i],root[i-1],get_id(a[i]));
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            int len=r-l+1;
            int lb=1,rb=len,ans=0;
            while(lb<=rb){
                int h=(lb+rb)>>1;
                int k=len-h+1;//
                int id=query(1,n,root[l-1],root[r],k);
                if(v[id-1]>=h){
                    //此时判断区间中是否有 h 个数大于等于 h；
                    ans=max(h,ans);
                    lb=h+1;
                }else
                    rb=h-1;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}