莫队 $O(n \sqrt{n} \log n)$：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,a[200010],B;
int lowbit(int x){
	return x&(-x);
}
struct N{
	int tr[200010];
	void add(int x,int v){
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	int find(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
}tr;
int get(){
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(tr.find(mid)>=mid)l=mid;
		else r=mid-1;
	}
	return l;
}
struct Q{
	int l,r,id;
}qq[200010];
bool cmp(Q a,Q b){
	if(a.l/B!=b.l/B)return a.l<b.l;
	return (a.l/B&1)?a.r>b.r:a.r<b.r;
}
int ans[200010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=q;i++){
		cin>>qq[i].l>>qq[i].r;
		qq[i].id=i;
	}
	sort(qq+1,qq+1+q,cmp);
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		while(l>qq[i].l)tr.add(a[--l],1);
		while(r<qq[i].r)tr.add(a[++r],1);
		while(l<qq[i].l)tr.add(a[l++],-1);
		while(r>qq[i].r)tr.add(a[r--],-1);
		ans[qq[i].id]=get();
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

整体二分 $O(n \log^2 n)$：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,a[200010],ans[200010];
vector<int> v[200010];
int lowbit(int x){
	return x&(-x);
}
struct N{
	int tr[200010];
	void add(int x,int v){
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	int find(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
}tr;
struct Q{
	int l,r,id;
}qq[200010],u1[200010],u2[200010];
void solve(int l,int r,int x,int y){
	if(l==r){
		for(int i=x;i<=y;i++){
			ans[qq[i].id]=l;
		}
		return ;
	}
	int mid=(l+r+1)>>1;
	for(int i=mid;i<=r;i++){
		for(int j:v[i]){
			tr.add(j,1);
		}
	}
	int n1=0,n2=0;
	for(int i=x;i<=y;i++){
		if(tr.find(qq[i].r)-tr.find(qq[i].l-1)>=mid)u2[++n2]=qq[i];
		else u1[++n1]=qq[i];
	}
	int id=x;
	for(int i=1;i<=n1;i++)qq[id++]=u1[i];
	for(int i=1;i<=n2;i++)qq[id++]=u2[i];
	solve(l,mid-1,x,x+n1-1);
	for(int i=mid;i<=r;i++){
		for(int j:v[i]){
			tr.add(j,-1);
		}
	}
	solve(mid,r,x+n1,y);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v[a[i]].push_back(i);
	}
	for(int i=1;i<=q;i++){
		cin>>qq[i].l>>qq[i].r;
		qq[i].id=i;
	}
	solve(1,n,1,q);
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

主席树+二分 $O(n \log^2 n)$：

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int n,q,a[200010],rt[200010],id;
struct N{
	int ls,rs,c; 
}tr[4000010];
void change(int pre,int &now,int l,int r,int x){
	now=++id;
	tr[now]=tr[pre];
	tr[now].c++;
	if(l==r){
		return ; 
	} 
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(pre),lc(now),l,mid,x);
	else change(rc(pre),rc(now),mid+1,r,x);
}
int find(int pre,int now,int l,int r,int x,int y){
	if(now==pre)return 0;
	if(l>=x&&r<=y)return tr[now].c-tr[pre].c;
	int mid=(l+r)>>1,ans=0;
	if(x<=mid)ans+=find(lc(pre),lc(now),l,mid,x,y);
	if(y>mid)ans+=find(rc(pre),rc(now),mid+1,r,x,y);
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		change(rt[i-1],rt[i],1,n,a[i]);
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		int l=1,r=n;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(find(rt[x-1],rt[y],1,n,mid,n)>=mid)l=mid;
			else r=mid-1;
		}
		cout<<l<<'\n';
	}
	return 0;
}

主席树上二分 $O(n \log n)$：

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int n,q,a[200010],rt[200010],id;
struct N{
	int ls,rs,c; 
}tr[4000010];
void change(int pre,int &now,int l,int r,int x){
	now=++id;
	tr[now]=tr[pre];
	tr[now].c++;
	if(l==r){
		return ; 
	} 
	int mid=(l+r+1)>>1;
	if(x<mid)change(lc(pre),lc(now),l,mid-1,x);
	else change(rc(pre),rc(now),mid,r,x);
}
int find(int pre,int now,int l,int r,int k){
	if(l==r)return l;
	int mid=(l+r+1)>>1,ans=0;
	if(tr[rc(now)].c-tr[rc(pre)].c>=mid-k)return find(rc(pre),rc(now),mid,r,k);
	else return find(lc(pre),lc(now),l,mid-1,k+(tr[rc(now)].c-tr[rc(pre)].c));
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		change(rt[i-1],rt[i],1,n,a[i]);
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		cout<<find(rt[x-1],rt[y],1,n,0)<<'\n';
	}
	return 0;
}

前置知识：普通莫队

前言：

熟悉的区间询问，熟悉的数据范围。嗯？好！上莫队！

由于本人做这道题时是初学莫队，根本不知道还有值域分块这种东西，好像所有的莫队都可值域分块，其他大佬的题解里要么用了主席树和整体二分 ( 蒟蒻太弱啦，根本不会！) ，要么都是值域分块莫队，所以这里给出一种普通莫队的做法。

想要 $\Theta (1)$ 转移当前答案看起来不太可做，但我们考虑答案在什么情况才会改变。

• k 表当前答案，sum 表后缀和。

1. 当 sum[k+1] > k ：k + 1 。

2. 当 sum[k] < k : k - 1 。

根据这两个性质，我们可以开一个桶维护每个数的出现次数，再用一个数维护大于等于 k 的数有多少个。在每次增 / 删数时检查是否需要更改答案就行了。在每次询问结束后更新答案也行。

然后就做到 $\Theta(1)$ 转移和查询答案啦！

最后附上代码:

#include <bits/stdc++.h>
using namespace std;
int read() {
	int x=0; char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}
void put(int x) {
	if(x>=10) put(x/10);
	putchar(x%10^48);
}
const int Maxn=2e5+10;
int n,q,unit,a[Maxn],cnt[Maxn],ans[Maxn];
struct node {
	int l,r,id;
	bool operator<(const node &b) const {
		if(l/unit!=b.l/unit) return l<b.l;
		return l/unit&1?r<b.r:r>b.r;
	}
} ask[Maxn];
signed main() {
	n=read(),q=read(),unit=sqrt(n);
	for(register int i=1; i<=n; ++i) a[i]=read();
	for(register int i=1; i<=q; ++i) ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
	sort(ask+1,ask+q+1);
	register int l=ask[1].l,r=ask[1].l-1,k=0,t=0;
	for(register int i=1; i<=q; ++i) {
		while(l>ask[i].l) ++cnt[a[--l]],t+=(a[l]>=k);
		while(r<ask[i].r) ++cnt[a[++r]],t+=(a[r]>=k);
		while(l<ask[i].l) t-=(a[l]>=k),--cnt[a[l++]];
		while(r>ask[i].r) t-=(a[r]>=k),--cnt[a[r--]];
		while(t-cnt[k]>k) t-=cnt[k++];
		while(t<k) t+=cnt[--k]; 
		ans[ask[i].id]=k;
	}
	for(register int i=1;i<=q;++i) put(ans[i]),putchar('\n');
	return 0;
}