莫队

求区间出现次数最多元素的出现次数。

直接跑莫队，开桶记录值 $i$ 的出现次数 $w_i$ 和出现次数 $w_i$ 的出现次数 $s_{w_i}$。

如果当前值的出现次数比答案 $ans$ 更大，更新答案。删除元素时更新序列如果 $s_{ans} = 0$ 则令 $ans \leftarrow ans-1$，由于此次删除使得 $ans$ 减少，被删除的数的出现次数必定为 $ans - 1$。

注意元素取值可以为负，先行将输入数据加上 $10^5$ 以保证所有数字不小于 $0$。

块长取 $\dfrac{n}{\sqrt{q}}$ 等级，固定其为 $250$。总体时间复杂度 $O(n \sqrt{q})$。

#include<bits/stdc++.h>
using namespace std;
constexpr int B=250,ext=100'000;
struct Query{int i,l,r;};
int n,q,l,r,cnt,a[100'005],s[100'005],w[200'005],ans[200'005];
inline void add(int x){
    --s[w[x]],++w[x],++s[w[x]];
    if(w[x]>cnt) ++cnt;
}
inline void del(int x){
    --s[w[x]],--w[x],++s[w[x]];
    if(s[cnt]==0) --cnt;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) a[i]+=ext;
    vector<Query> v(q);
    for(auto &[i,l,r]:v) i=++cnt,scanf("%d%d",&l,&r);
    sort(v.begin(),v.end(),[](auto x,auto y){
        if(x.l/B!=y.l/B) return x.l<y.l;
        return (x.l/B)&1 ? x.r>y.r:x.r<y.r;
    });
    l=1,r=0,cnt=0;
    for(auto [i,ql,qr]:v){
        while(l>ql) add(a[--l]);
        while(r<qr) add(a[++r]);
        while(l<ql) del(a[l++]);
        while(r>qr) del(a[r--]);
        ans[i]=cnt;
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}