RT

正确性无误

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int b[200005];
int f[200005];
int cnt[200005];
map<int,int>mp;
int ans; 
struct node{
	int id,l,r,ans;
}ask[200005];
int n,m;
int Bsize;
bool cmp(node a,node b){
	if(a.l/Bsize==a.r/Bsize){
		if((int)((a.l-1)/Bsize+1)&1)return a.r<b.r;
		return a.r>b.r;
	}
	return a.l<b.l;
}
void add(int t){
	f[cnt[a[t]]++]--;
	f[cnt[a[t]]]++;
	ans=max(ans,cnt[a[t]]);
}
void del(int t){
	if(f[cnt[a[t]]]==1&&cnt[a[t]]==ans)ans--;
	f[cnt[a[t]]--]--;
	f[cnt[a[t]]]++;
}
bool Cmp(node a,node b){
	return a.id<b.id;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	Bsize=sqrt(n);
	int cnt=0;
	for(int i=1;i<=m;i++){
		cin>>ask[i].l>>ask[i].r;
		ask[i].id=i;
	}
	for(int i=1;i<=n;i++){
		if(b[i]!=b[i-1])mp[b[i]]=++cnt;
	}
	for(int i=1;i<=n;i++){
		a[i]=mp[a[i]];
	}
	sort(ask+1,ask+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>ask[i].l)add(--l);
		while(r<ask[i].r)add(++r);
		while(l<ask[i].l)del(l++);
		while(r>ask[i].r)del(r--);
		ask[i].ans=-ans;
	}
	sort(ask+1,ask+m+1,Cmp);
	for(int i=1;i<=m;i++)cout<<ask[i].ans<<endl;
	return 0;
}