因为$max$运算无法撤销,所以我们的莫队不能有删点操作,如果只加点的话,考虑$r$是排过序的,可以直接扫过去,$l$在同一个块里,这样可以$l$所在的块外信息保留并随着$r$更新,块内信息暴力计算
记块大小为$B$,每次暴力计算$l$所在的块的复杂度贡献为$B$,$r$需要遍历块的数量次整个序列,块数量为$\displaystyle\frac{n}{B}$,取 $B = \sqrt{n}$,最优复杂度为$O(\sqrt{n})$
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e6 + 10, inf = 0x3f3f3f3f;
const long long Linf = 0x3f3f3f3f3f3f3f3f;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
struct QRY {
int l, r, id;
} qry[N];
int n, m, cnt[N], val[N], col[N], C, L[N], R[N], bel[N], b[N];
long long ans[N];
void init() {
int B = sqrt(n);
for (int i = 1; i <= n; i += B) {
L[++C] = i; R[C] = i + B - 1;
}
for (int i = 1; i <= C; i++) {
for (int j = L[i]; j <= R[i]; j++) bel[j] = i;
}
}
bool cmp(QRY a, QRY b) {
return bel[a.l] == bel[b.l] ? a.r < b.r : bel[a.l] < bel[b.l];
}
int main() {
n = read(); m = read(); init();
for (int i = 1; i <= n; i++) val[i] = read(), b[i] = val[i];
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) col[i] = lower_bound(b + 1, b + n + 1, val[i]) - b;
for (int i = 1; i <= m; i++) qry[i] = (QRY){read(), read(), i};
sort(qry + 1, qry + m + 1, cmp);
for (int k = 1, i = 1; k <= C; k++) {
int r = R[k]; long long res = 0, tmp = 0;
while (bel[qry[i].l] == k) {
while (r < qry[i].r) r++, cnt[col[r]]++, res = max(res, 1ll * cnt[col[r]] * val[r]);
tmp = res;
for (int j = qry[i].l; j <= min(R[k], qry[i].r); j++) cnt[col[j]]++, res = max(res, 1ll * cnt[col[j]] * val[j]);
ans[qry[i].id] = res;
for (int j = qry[i].l; j <= min(R[k], qry[i].r); j++) cnt[col[j]]--; res = tmp; i++;
}
for (int j = R[k] + 1; j <= r; j++) cnt[col[j]]--;
}
for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
return 0;
}