撰写原题链接：
https://www.luogu.org/problem/AT1219
https://www.lydsy.com/JudgeOnline/problem.php?id=4241
人话题面： 给定一个长为n的序列，q次询问区间\([l,r]\)上【出现的数字a×它的出现次数\(cnt_a\)】的最大值
既然是如此熟悉的，查询区间上不同的数的个数，肯定会先想到用莫队来维护最大值，但是原来的莫队不完全适用了，维护最大值添加起来很容易，但是没办法删除（如果你超级强说不定可以但我不会），我能想到的只有\(O(n)\)暴力，显然不行。所以就有了：回滚莫队
我们都很清楚莫队对询问区间的排序方法带来的一种性质：左端点在同一个分块中的所有查询区间右端点单调递增。所以对于左端点在同一个块中的每个区间，我们都可以\(O(n)\)解决所有的右端点，并且由于右端点的单调递增，我们不需要回头删除数据。若分块时以\(\sqrt n\)为块的大小，那么一共有\(\sqrt n\)个块，所以复杂度为\(O(n\sqrt n)\)。【由于左端点在一个块中是无序的，所以我们可以将一个块内的左端点统一记为块的右端，每次查询到一个区间，就把左区间暴力移动到该查询区间的左端点，最坏移动\(\sqrt n\)次，有n个左端点，复杂度也为\(O(n\sqrt n)\)】
如果左右端点都在同一个分块中，那么显然这里暴力统计的最坏复杂度也只是\(O(\sqrt n)\)，所以直接暴力。
综上我们可以看到，回滚莫队的总复杂度也还是\(O(n\sqrt n)\)【可以这样想，回滚莫队就是比普通莫队多了个右端点的\(O(n\sqrt n)\)的左移而已】。
这样子的复杂度过这一道题没有问题，莫队万岁！！！
代码：
把这个代码调对可是不容易呢！！！因为ATCoder的数据点太多了。洛谷RemoteJudge太慢了，建议左转BZOJ！
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=100100;
const int N=5050;
int n,m;
int a[M],b[M],c[M],be[M],cnt[M],cunt[M],br[M];
ll ans[M];
struct ques{
int l,r,id;
}q[M];
inline int Read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
inline bool CMP(ques a,ques b){
return (be[a.l]^be[b.l])?be[a.l]<be[b.l]:a.r<b.r;
}
int main(){
n=Read(),m=Read();
int sq=sqrt(n),up=ceil((double)n/sq);
for(int i=1;i<=up;i++){
br[i]=i*sq;
for(int j=(i-1)*sq+1;j<=br[i];j++)
be[j]=i;
}
br[up]=n;
for(int i=1;i<=n;i++)
a[i]=b[i]=Read();
sort(a+1,a+n+1);
int tot=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;i++)
c[i]=lower_bound(a+1,a+tot+1,b[i])-a;
for(int i=1;i<=m;i++){
q[i].l=Read();
q[i].r=Read();
q[i].id=i;
}
sort(q+1,q+m+1,CMP);
int i=1;
for(int k=0;k<=up;k++){
int l=br[k]+1,r=br[k];
ll now=0;
memset(cnt,0,sizeof(cnt));
for(;be[q[i].l]==k;i++){
int ql=q[i].l,qr=q[i].r;
ll tmp;
if(be[ql]==be[qr]){
tmp=0;
for(int j=ql;j<=qr;j++)
cunt[c[j]]=0;
for(int j=ql;j<=qr;j++)
tmp=max(tmp,1ll*++cunt[c[j]]*b[j]);
ans[q[i].id]=tmp;
continue;
}
while(r<qr)
now=max(now,1ll*++cnt[c[++r]]*b[r]);
tmp=now;
while(l>ql)
now=max(now,1ll*++cnt[c[--l]]*b[l]);
ans[q[i].id]=now;
while(l<br[k]+1)
--cnt[c[l++]];
now=tmp;
}
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}