Steven_Meng's Blog

传送门

首先，如果这道题用的是普通的莫队，那么删除元素的时候，可能出现次数最大的那个元素的出现次数被减少至小于出现次数第二大的那个元素的出现次数，此时，你就没法知道出现次数第二大的元素的值，就咕咕了。

当然你也可以用一个$\rm set$搞，但是估计会$\rm TLE$

这里要介绍一种莫队，叫做回滚莫队。

先考虑莫队的排序方式，我们把整个序列分块，以左端点所在的块的编号为第一关键字，右端点所在的块的编号为第二关键字来排序。

不妨分块考虑，我们钦定左端点，让它就在其中一个块里面，当然右端点我们管不着。

如图，左端点$l$在蓝色区域，右端点$r$在红色区域。

根据排序的方式，发现右端点一直递增。

设蓝色区域左端点是$L$，右端点是$R$

分情况讨论：

1.$r \le R$

这时我们查询的就是类似于绿色区域的东东，暴力搞就可以了，时间复杂度为$O(\sqrt n)$

2.$r>R$

这时我们查询的就是类似于绿色区域的东东，不妨把绿色区域分成两块：

分成了$[l,R],[R+1,r]$两块，发现$[R+1,r]$非常好搞，因为$r$ 是递增的，所以移动$r$过程中统计即可。

但是$[l,R]$不好搞，$l$没有单调性。

别忘了我们钦定了$l$在同一块，所以暴力移动$l$，时间复杂度$O (\sqrt n)$，最后别忘了还原$l$。

所以，钦定$l$ 这种思路非常巧妙，不知道高到哪里去了。

形象一点来说，$l$的移动非常繁忙，每来一个$r$都要在块内移动一个来回，但是$r$非常轻松，只要一直往右移动就行了。

代码如下，注意开$\text{long long}$

我感觉写起来不怎么优美。

#include <bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],b[MAXN],org[MAXN],pos[MAXN],n,m;
struct Query{
    int l,r;
    int id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){
    return pos[A.l]==pos[B.l]?A.r<B.r:pos[A.l]<pos[B.l];
}
inline void discrete(){
    for (register int i=1;i<=n;++i) b[i]=a[i];
    sort(b+1,b+1+n);
    int s=unique(b+1,b+1+n)-b-1;
    for (register int i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+1+s,a[i])-b;
    }
}
int Size,cnt[MAXN],Ans[MAXN];
inline int BruteForce(int l,int r){
    //这里不能直接memset不然就不是O(sqrt(n))的了
    for (register int i=l;i<=r;++i) cnt[a[i]]=0;
    int ret=0;
    for (register int i=l;i<=r;++i) {
        ret=max(ret,org[i]*(++cnt[a[i]]));
    }
    return ret;
}
int c[MAXN],ans;
inline void Add(int x){
    ans=max(ans,org[x]*(++c[a[x]]));
}
inline void Del(int x){
    --c[a[x]];
}
inline int MoQueue(int i,int id){//返回下一个块的第一个询问的编号
    int R=min(n,Size*id);
    int l=R,r=R-1;
    ans=0;
    memset(c,0,sizeof(c));
    while (pos[q[i].l]==id){
        if (pos[q[i].l]==pos[q[i].r]) {
            Ans[q[i].id]=BruteForce(q[i].l,q[i].r);
            i++;
            continue;
        }
        while (r<q[i].r) Add(++r);
        int temp=ans;//记录的是[R+1,r]的答案
        while (l>q[i].l) Add(--l);
        Ans[q[i].id]=ans;
        while (l<R) Del(l++);
        ans=temp;
        i++;
    }
    return i;
}
#undef int
int main(){
#define int long long
    n=read(),m=read();
    Size=(int)(sqrt(n));
    for (register int i=1;i<=n;++i){
        org[i]=a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    discrete();
    for (register int i=1;i<=m;++i){
        int l=read(),r=read();
        q[i]=Query{l,r,i};
    }
    sort(q+1,q+1+m);
    int ptr=1;
    for (register int i=1;i<=pos[n];++i){
        ptr=MoQueue(ptr,i);
    }
    for (register int i=1;i<=m;++i){
        printf("%lld\n",Ans[i]);
    }
}