题意：就是求区间内第k大的值大于等于k时的最大的k。
思路：很明显二分求这个最大的k，再用主席树求第k大的值来判断是否大于等于k。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn],rt[maxn*20],ls[maxn*20],rs[maxn*20],sum[maxn*20];
int cnt,ql,qr,k;
void build(int& o,int l,int r)
{
o=++cnt;
sum[o]=0;
if(l==r)
return;
int m=(l+r)/2;
build(ls[o],l,m);
build(rs[0],m+1,r);
}
void update(int pre,int& o,int l,int r,int pos)
{
o=++cnt;
ls[o]=ls[pre];
rs[o]=rs[pre];
sum[o]=sum[pre]+1;
if(l==r)
return;
int m=(l+r)/2;
if(pos<=m)
update(ls[pre],ls[o],l,m,pos);
else
update(rs[pre],rs[o],m+1,r,pos);
}
int query(int pre,int o,int l,int r)
{
if(l==r)
return b[l];
int m=(l+r)/2;
int cmp=sum[ls[o]]-sum[ls[pre]];
if(cmp>=k)
return query(ls[pre],ls[o],l,m);
else
{
k-=cmp;
return query(rs[pre],rs[o],m+1,r);
}
}
void work(int sz)
{
scanf("%d%d",&ql,&qr);
int L=1,R=qr-ql+2,m;//把最大值＋1，去解决二分自带的bug
while(L<R)
{
m=(L+R)/2;
k=qr-ql+1+1-m;
int t=query(rt[ql-1],rt[qr],1,sz);
if(t>=m)
{
if(L==m)
break;
L=m;
}
else
R=m;
}
printf("%d\n",m);
}
int main()
{
int n,q,i;
while(~scanf("%d%d",&n,&q))
{
for(i=1;i<=n;i++)
{
scanf("%d",&b[i]);
a[i]=b[i];
}
sort(b+1,b+n+1);
int sz=unique(b+1,b+1+n)-(b+1);
cnt=0;
build(rt[0],1,sz);
for(i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+sz,a[i])-b;
for(i=1;i<=n;i++)
update(rt[i-1],rt[i],1,sz,a[i]);
while(q--)
work(sz);
}
}