大致题意
给定一个长度为 n 的数列 ai，m 次询问。每次询问区间 [l,r] 的等级，一个区间的等级定义为 最大的i 满足区间内大于等于 i 的值的个数也大于等于 i 。 （1<=n<=1e5，1<=ai<=n)
思路
ai的值比较小，可以直接不用离散化主席树，每次查询区间 [l,r]的答案的时候，二分答案，在主席树上查询权值区间 [mid,n]的数的个数是否大于等于mid即可判断。复杂度nlognlogn。 牛客测评姬跳的厉害，同样的代码多交了几次居然就过了。不知道是不是假算法。
更新，赛后看运行比较快的代码，果然是nlogn的算法，就是主席树搜索答案的时候，直接顺便查询右侧的和是否大于mid ，如果满足则向右搜，然后就可以一直查询到答案，不需要二分答案。其实搜索向下的过程就是二分答案的过程和策略。%%%
代码
#include<bits/stdc++.h>
using namespace std
;
#define maxn 100005
#define maxm 1006
#define ll long long int
#define INF 0x3f3f3f3f
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) (x*x)
#define inf (ll)2e18+1
#define PI acos(-1)
#define mod 10007
#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)
ll
read(){
ll x
=0,f
=1ll;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}
while(isdigit(ch
))x
=x
*10+ch
-'0',ch
=getchar();
return f
*x
;
}
int n
,m
,a
[maxn
];
int cnt
,root
[maxn
];
struct node
{int l
,r
,sum
;}T
[maxn
*20];
void update(int l
,int r
,int &x
,int y
,int pos
){
T
[++cnt
]=T
[y
],T
[cnt
].sum
++,x
=cnt
;
if(l
==r
)return ;
int mid
=(l
+r
)/2;
if(mid
>=pos
)update(l
,mid
,T
[x
].l
,T
[y
].l
,pos
);
else update(mid
+1,r
,T
[x
].r
,T
[y
].r
,pos
);
T
[x
].sum
=T
[T
[x
].l
].sum
+T
[T
[x
].r
].sum
;
}
int query(int l
,int r
,int x
,int y
,int lp
,int rp
){
if(lp
<=l
&&r
<=rp
)return T
[y
].sum
-T
[x
].sum
;
int mid
=(l
+r
)/2;
int res
=0;
if(lp
<=mid
)res
+=query(l
,mid
,T
[x
].l
,T
[y
].l
,lp
,rp
);
if(mid
+1<=rp
) res
+=query(mid
+1,r
,T
[x
].r
,T
[y
].r
,lp
,rp
);
return res
;
}
int main()
{
while(~scanf("%d%d",&n
,&m
)){
cnt
=0;
inc(i
,1,n
)a
[i
]=read();
inc(i
,1,n
)update(1,n
,root
[i
],root
[i
-1],a
[i
]);
int x
,y
;
inc(i
,1,m
){
x
=read();y
=read();
int l
=1,r
=n
,ans
=1;
while(l
<=r
){
int mid
=(l
+r
)>>1;
if(query(1,n
,root
[x
-1],root
[y
],mid
,n
)>=mid
){
ans
=mid
;
l
=mid
+1;
}
else r
=mid
-1;
}
printf("%d\n",ans
);
}
inc(i
,0,cnt
)T
[i
].l
=T
[i
].r
=T
[i
].sum
=0;
inc(i
,0,n
)root
[i
]=0;
}
return 0;
}
