Time limit 3000 ms

Memory limit 132768 kB

OS Windows

Source CCPC2018-湖南全国邀请赛-重现赛（感谢湘潭大学）

一个序列，每次询问一个区间，要求一个最大的h，使区间内有h个数字大于等于h。

我用的在线做法，主席树套二分，对于每个区间，二分k的值，看看这个第k大的数是否大于等于k（是否有k个大于等于k的数）

• 如果大于等于（前k大的数都大于等于k），那么就更新答案，并且将增大k的值（\(ll=mid+1\)）
• 如果小于（前k大的数存在小于k的），那么就减小k的值（\(rr=mid-1\)）

由于主席树板子是求第k小的，所以二分那里做了些变化，转换成第k大。

网上还有离线做法：莫队套权值树状数组套二分，我先留坑。

#include<stdio.h>
#include<algorithm>
int n,m;
int a[100010];

struct Node{
    int lson,rson;
    int sum;
}t[4000010];
int root[100010],cnt;
void build(int &x,int l,int r)
{
    x=cnt++;
    t[x]={0,0,0};
    if(l==r)
    {
        t[x].sum=1;
        return;
    }
    int mid=l+r>>1;
    build(t[x].lson,l,mid);
    build(t[x].rson,mid+1,r);
    t[x].sum=t[t[x].lson].sum+t[t[x].rson].sum;
}
void update(int &x,int pre,int l,int r,int pos)
{
    x=cnt++;
    t[x] = t[pre];
    t[x].sum++;
    if(l==r) return;
    int mid=l+r>>1;
    if(pos<=mid)
        update(t[x].lson,t[pre].lson,l,mid,pos);
    else
        update(t[x].rson,t[pre].rson,mid+1,r,pos);
}
int que(int x,int pre,int l,int r,int k)
{
    if(l==r) return l;
    int delta=t[t[x].lson].sum-t[t[pre].lson].sum,mid=l+r>>1;
    if(k<=delta)
        return que(t[x].lson,t[pre].lson,l,mid,k);
    else
        return que(t[x].rson,t[pre].rson,mid+1,r,k-delta);
}

int main()
{
    freopen("test.in","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        build(root[0],1,n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            update(root[i],root[i-1],1,n,a[i]);
        }
        int l,r;
        while(m--)
        {
            scanf("%d%d",&l,&r);

            int ll=1,rr=(r-l+1),ans=0;
            while(ll<=rr)
            {
                int mid=ll+rr>>1,kk=r-l+1-mid+1;//第mid大<=>第kk小
                int temp=que(root[r],root[l-1],1,n,kk);//第mid大的数是temp；

                if(temp>=mid) ans=std::max(ans,mid),ll=mid+1;
                else rr=mid-1;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}