```cpp
#include<bits/stdc++.h>
using namespace std;
#define MN 400005
#define int long long
void read(int &x){
int zf=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')zf=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=zf;
}
struct data{
int x,y,id,ans;
}w[MN];
bool cmp(data a,data b){
return a.x<b.y;
}
bool cmd(data a,data b){
return a.y<b.y;
}
bool cnm(data u,data v){
return u.id<v.id;
}
int n,m,a[MN],C[MN],sum[MN],tot[MN],T,L;
signed main(){
read(n);read(m);
T=(sqrt(m));L=m/T;
for(int i=1;i<=n;++i){
read(a[i]);
C[i]=a[i];
}
sort(C+1,C+1+n);
for(int i=1;i<=n;++i){
int mid,l=1,r=n+1;
while(l+1<r){
mid=(l+r)>>1;
if(C[mid]>a[i]) r=mid;
else l=mid;
}
a[i]=l;
}//离散化
for(int i=1;i<=m;++i){
read(w[i].x);read(w[i].y);
if(w[i].x>w[i].y) swap(w[i].x,w[i].y);
w[i].id=i;
}
sort(w+1,w+1+m,cmp);
for(int i=1;i<=T+1;++i){
int l=(i-1)*L+1,r=min(i*L,m);
if(l>r) break;
sort(w+l,w+r+1,cmd);
memset(sum,0,sizeof(sum));
memset(tot,0,sizeof(tot));
tot[0]=n;
for(int j=w[l].x;j<=w[l].y;++j){
tot[sum[a[j]]]--;
sum[a[j]]++;
tot[sum[a[j]]]++;
w[l].ans=max(sum[a[j]],w[l].ans);
}
for(int j=l+1;j<=r;++j){
w[j].ans=w[j-1].ans;
if(w[j].x>w[j-1].x)
for(int k=w[j-1].x;k<w[j].x;++k){
tot[sum[a[k]]]--;
if(!tot[sum[a[k]]]&&w[j].ans==sum[a[k]]) w[j].ans--;
sum[a[k]]--;
tot[sum[a[k]]]++;
}
else for(int k=w[j].x;k<w[j-1].x;++k){
tot[sum[a[k]]]--;
sum[a[k]]++;
tot[sum[a[k]]]++;
w[j].ans=max(w[j].ans,sum[a[k]]);
}
for(int k=w[j-1].y+1;k<=w[j].y;++k){
tot[sum[a[k]]]--;
sum[a[k]]++;
tot[sum[a[k]]]++;
w[j].ans=max(w[j].ans,sum[a[k]]);
}
}
}//莫队
sort(w+1,w+1+m,cnm);
for(int i=1;i<=m;++i)
printf("-%lld\n",w[i].ans);
return 0;
}
```
by skydogli @ 2019-03-06 12:51:31
我试了一下,输入w后sort 就会报错
by skydogli @ 2019-03-06 12:53:49
没事,你只要在一个好学校,就算这题只能拿到10分,也可以进队了.
by 夜卿羽 @ 2019-03-06 13:15:09
我TMD怎么也没想到,cmp打错了。。。。
by skydogli @ 2019-03-06 14:49:10