AT1219 歴史の研究

因为$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;
}