【题解】历史研究 回滚莫队 bzoj4241 ——quhengyi11

传送喵

吐槽

回滚莫队，顾名思义就是将莫队像滚雪球一样滚成一团超可爱的样子

题解

因为在上 lxl 的 luogu 网课的时候他提到维护一些不滋磁删除操作的信息 (比如取 $max$) 可以用不删除元素的莫队来实现，在网上查了查这东西叫回滚莫队。

脑补了一下如果不滋磁删除的话难道要把所有询问建一个类似包含关系的树结构然后从底自上维护答案而且还会被构造数据卡，当时 lxl 并没有补充所以就很疑惑 $QAQ$

其实这个算法思路挺简单的，对于在一个块中的询问区间的左端点，我们按它们的右端点从小到大排序，然后记当前左端点所在块的最右边的点的右边一个位置为 $pl$(其实就是下一个块的第一个点) 每一次令当前的左端点 $L$变为 $pl$，然后将右端点移到当前询问的右端点的位置，然后记录当前答案为 $cur$，也就是说 $cur$表示的是 $[pl,q[i].r]$的答案，然后再扩展 $L$到 $q[i].l$记录当前答案，当到下一个询问 $q[i+1]$的时候 (假定它的左端点和前面一个询问的左端点在同一个块里)，那么我们可以将左右端点赋值成 $pl$和 $q[i].r$并把当前答案 $ans$更新为 $cur$，容易知道 $q[i+1].l\geq pl$且 $q[i+1].r \geq q[i].r$，所以保证了维护的答案没有删除，这个操作我们一般把它叫做撤销。

容易发现复杂度跟普通莫队是一样的，只是常数会稍微大一点。

所以这其实是一篇讲算法的 blog

因为题目是裸的回滚莫队所以不讲了。

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define Re register
#define N 100005
#define mod 1004535809
#define ll long long 
int n, m, a[N], sq, bl[N], u[N], tot;
ll ans[N];
struct node{
    int l, r, id;
    friend bool operator < (node x, node y)
    {
        return bl[x.l] == bl[y.l] ? x.r < y.r : x.l < y.l;
    }
}q[N];
ll tmp[N];
inline ll calc (int l, int r)
{
    ll ret = 0;
    fo (i, l, r) tmp[a[i]] = 0;
    fo (i, l, r) {++tmp[a[i]]; ret = std::max(ret, tmp[a[i]] * u[a[i]]);}
    return ret;
}
ll now, cur, cnt[N];
inline void add (int x)
{
    ++cnt[x];
    now = std::max(now, cnt[x] * u[x]);
}
inline void del (int x)
{
    --cnt[x];
}
inline void modui ()
{
    cur = 0, now = 0;
    int L = sq, R = L - 1, pl = L;
    fo (i, 1, m)
    {
        if (bl[q[i - 1].l] < bl[q[i].l])
        {
            L = (bl[q[i].l] + 1) * sq; R = L - 1;
            memset(cnt, 0, sizeof cnt);
            pl = L;
            cur = now = 0;
        }
        if (bl[q[i].l] == bl[q[i].r]) {ans[q[i].id] = calc(q[i].l, q[i].r); continue;}
        while (R < q[i].r) add(a[++R]);
        cur = now; 
        while (q[i].l < L) add(a[--L]);
        ans[q[i].id] = now;
        while (L < pl) del(a[L++]);
        now = cur;
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    sq = (int) sqrt(n);
    fo (i, 1, n) {scanf("%d", &a[i]); bl[i] = i / sq; u[i] = a[i];}
    std::sort(u + 1, u + n + 1);
    tot = std::unique(u + 1, u + n + 1) - u - 1;
    fo (i, 1, n) a[i] = std::lower_bound(u + 1, u + tot + 1, a[i]) - u;
    fo (i, 1, m)
    {
        scanf("%d %d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1);
    modui();
    fo (i, 1, m)
        printf("%lld\n", ans[i]);
    return 0;
}