#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+10;;
int n,m;
int block_size,pos[N];
int v[N];
struct Q
{
int l,r,k;
}question[M];
int ans[M],res=0;
map<int,int> cnt;
//priority_queue<pair<int,pair<int,int> > >que;
int book[N];
void Add(int x,bool y)
{
book[cnt[v[x]]]--;
cnt[v[x]]++;
book[cnt[v[x]]]++;
res=max(res,cnt[v[x]]);
}
void Sub(int x,bool y)
{
book[cnt[v[x]]]--;
if(book[cnt[v[x]]]==0 and cnt[v[x]]==res)res--;
cnt[v[x]]--;
book[cnt[v[x]]]++;
}
int main()
{
while(cin>>n)
{
if(n==0)break;cin>>m;
block_size=sqrt(n);
cnt.clear();
memset(book,0,sizeof(book));
for(int i=1;i<=n;i++)
{
cin>>v[i];pos[i]=i/block_size;
}
for(int i=0;i<m;i++)
{
cin>>question[i].l>>question[i].r;
question[i].k=i;
}
sort(question,question+m, [](Q x ,Q y)
{
return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
});
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(question[i].l<l) Add(--l,0);
while(question[i].r>r) Add(++r,1);
while(question[i].l>l) Sub(l++,0);
while(question[i].r<r) Sub(r--,1);
ans[question[i].k]=res;
}
for(int i=0;i<m;i++)
cout<<ans[i]<<endl;
}
return 0;
}
我真的崩溃了,再也不想做外国oj的题了,还没有数据给我我测试。
我用的是莫队,请大佬调教我的代码(哭哭哭)