@[Failure_Creator](/user/486677)
这样:
```cpp
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e6 + 10;
int a[N], cnt[N], ans[N], sk[N];
struct node {
int l, r, id, bel;
bool operator < (const node & o) const {
if(bel == o.bel) return r < o.r;
return bel < o.bel;
}
} qry[N];
int cur = -N;
vector <int> vec;
inline int query(int x) {
return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}
void add(int x) {
sk[++cnt[a[x]]]++;
if(cnt[a[x]] > cur)
cur = cnt[a[x]];
}
void del(int x) {
if(cnt[a[x]] == cur && sk[cnt[a[x]]] == 1)
cur--;
sk[cnt[a[x]]--]--;
}
int main() {
int n; scanf("%d", &n);
int m; scanf("%d", &m);
int siz = sqrt(n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), vec.push_back(a[i]);
for (int i = 1; i <= n; ++i)
a[i] = query(a[i]);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &qry[i].l, &qry[i].r);
qry[i].id = i; qry[i].bel = (qry[i].l - 1) / siz + 1;
}
sort(qry + 1, qry + m + 1);
int l = 1, r = 0;
for (int i = 1; i <= m; ++i) {
while(l < qry[i].l) del(l++);
while(l > qry[i].l) add(--l);
while(r < qry[i].r) add(++r);
while(r > qry[i].r) del(r--);
ans[qry[i].id] = cur;
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
}
```
by midsummer_zyl @ 2024-01-06 17:06:06