2018湘潭邀请赛C题（主席树+二分）

 

题目地址：https://www.icpc.camp/contests/6CP5W4knRaIRgU

比赛的时候知道这题是用主席树+二分，可是当时没有学主席树，就连有模板都不敢套，因为代码实在是太长了。

 

题意：给你一些数字，要求你某些区间中找到一个h-index。

每次查找h-index复杂度不能超过O（n）

h-index的定义是：有最少h个数不小于h，找到最大的h。

 

分析：假如查询的区间长度为n，那么ans一定是1-n。用二分查找找到一个最大的n即可

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
struct Tree
{
     int L,R,num;
}tree[maxn*20];
int root[maxn];
int cnt;
void updata(int x,int &rt,int a,int b)
{
     tree[cnt++]=tree[rt];
     rt=cnt-1;
     tree[rt].num++;
     if(a==b)return;
     int mid=(a+b)/2;
     if(x>=mid+1)
         updata(x,tree[rt].R,mid+1,b);
     else
         updata(x,tree[rt].L,a,mid);
}
int quer(int a,int b,int k,int s,int o)
{
    if(s==o)return s;
    int d=tree[tree[b].L].num-tree[tree[a].L].num;
    int mid=(s+o)/2;
    if(k<=d)
        return quer(tree[a].L,tree[b].L,k,s,mid);
    else
        return quer(tree[a].R,tree[b].R,k-d,mid+1,o);
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        cnt=1;
        for(int i=1;i<=n;i++)
        {
            root[i]=root[i-1];
            int num;
            scanf("%d",&num);
            updata(num,root[i],1,n);
        }
        for(int i=1;i<=m;i++)
        {
            int l,r;
            scanf("%d %d",&l,&r);
            int b=r-l+1,a=1;
            int mid=(a+b)/2;
            while(a!=b)
            {
                if(quer(root[l-1],root[r],r-l+1-mid,1,n)>=mid+1)
                    a=mid+1;
                else
                    b=mid;
                mid=(a+b)/2;
            }
            printf("%d\n",a);
        }
    }
    return 0;
}