带修时间操控者，回滚暴力压路机
分析题目，没有修改，只有问询，似乎只是一个普通莫队。但如果用普通莫队去做就会发现写不了删点操作，因为无法确定删除掉的是不是最大的那个(如果强行做好像也行，不过要写一个数据结构来维护每个事件的重要度并保持单调，感觉好麻烦)。
所以我们就改变一下思路：既然删点难写那么咱们就改变思路：不删点。
但每个问询区间大小不一，无法保持只加点不删点。其实可以保持右端点只增不减，对于左端每次增点后用暴力把增点数据删除（即回滚）即可。
对于右端点只增不减很好实现，排序函数这么写

bool cmp(const Query &a, const Query &b) {
    int i = get(a.l), j = get(b.l);
    if (i != j)
        return i < j;
    return a.r < b.r;
}

针对左端的数据删除，我们用暴力遍历增点路径，对计数数组进行回退(删掉之前的增点)。在左端点增点前要拷贝一份当前最大重要度，用于保证在左端增点，回滚后最大重要度不变。
具体处理方式：
1：从第一个分块开始，首先用暴力+回滚处理掉问询区间完全包含在该块内的问询。
2:对于问询左端在第一个分块，问询右端在第二个分块的问询。由于R是递增的，先完成R的增点，再用暴力＋回滚处理掉其位于第一个分块中的点。

此外要注意到x的范围是1e9，所以要用一次离散化。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m, len;
int w[N], cnt[N];
LL ans[N];
struct Query {
    int id, l, r;
} q[N];
vector<int> nums;//用于离散化的数组

int get(int x) {
    return x / len;
}

bool cmp(const Query &a, const Query &b) {//保证左端点固定，右端点递增
    int i = get(a.l), j = get(b.l);
    if (i != j)
        return i < j;
    return a.r < b.r;
}

void add(int x, LL &res) {
    cnt[x] ++ ;
    res = max(res, (LL)cnt[x] * nums[x]);//nums储存的是离散前的值
}

int main() {
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &w[i]), nums.push_back(w[i]);

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());//离散化操作

    for (int i = 1; i <= n; i ++ )
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();
        //计算离散的对应位置

    for (int i = 0; i < m; i ++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m, cmp);

    for (int x = 0; x < m;) {//一次for循环处理所有L在当前块的问询。
        int y = x;
        while (y < m && get(q[y].l) == get(q[x].l))//q[x]到q[y]问询的左端点在该块
            y ++ ;

        int right = get(q[x].l) * len + len - 1;//right就是当前块的最右端点


        while (x < y && q[x].r <= right) {//暴力处理问询区间全部在块内的
            LL res = 0;
            int id = q[x].id, l = q[x].l, r = q[x].r;
            for (int k = l; k <= r; k ++ )//暴力处理
                add(w[k], res);//w是离散值
            ans[id] = res;
            for (int k = l; k <= r; k ++ )//遍历结束后要变回来,这就是回滚
                cnt[w[k]] -- ;
            x ++ ;
        }

        // 求块外的询问
        LL res = 0;
        int i = right, j = right + 1;

        while (x < y) {
            int id = q[x].id, l = q[x].l, r = q[x].r;
            //由于排序时r是递增的,所以只需要一次遍历就能把这一堆问询解决
            while (i < r)
                add(w[ ++ i], res);//i是递增的
            LL backup = res;//备份
            while (j > l)
                add(w[ -- j], res);
            ans[id] = res;
            while (j < right + 1)//回滚操作操作,将数据和j都回滚回去
                cnt[w[j ++ ]] -- ;
            res = backup;
            x ++ ;
        }
        memset(cnt, 0, sizeof cnt);
    }

    for (int i = 0; i < m; i ++ )
        printf("%lld\n", ans[i]);
    return 0;
}