$n=10^5$，严格 $O(n\sqrt n)$ 的回滚莫队 TLE 了！

AtCoder 提交记录

代码有注释的：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
int n,m,a[N],old[N];
int in[N],bl[N],br[N];
int cnt[N];
ll res,tmp;
ll ans[N];
struct Query{
	int l,r,id;
} Q[N];
void isc(){
	for(int i=1;i<=n;i++) old[i]=a[i];
	sort(old+1,old+n+1);
	int tot=unique(old+1,old+n+1)-old-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(old+1,old+tot+1,a[i])-old;
} //离散化 
bool cmp(Query A,Query B){
	if(in[A.l]!=in[B.l]) return A.l<B.l;
	return A.r<B.r;
} 
void Add(int x,ll &res){res=max(res,(ll)old[x]*(++cnt[x]));} // 添加 
void Del(int x){cnt[x]--;} // 删除 
int main(){
	scanf("%d%d",&n,&m);
	int len=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),in[i]=(i-1)/len+1;
	for(int i=1;i<=in[n];i++) bl[i]=(i-1)*len+1,br[i]=min(i*len,n); // bl[i] 表示块 i 的左端点，br[i] 表示块 i 的右端点 
	isc(); 
	for(int i=1;i<=m;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+m+1,cmp); // 顺序询问 
	int lst=0;
	for(int i=1,l=1,r=0;i<=m;i++){
		int L=Q[i].l,R=Q[i].r,I=Q[i].id;
		if(in[L]!=lst){
			memset(cnt,0,sizeof(cnt));
			l=br[in[L]]+1,r=br[in[L]];
			res=0;
		} // L 所在块更新，O(n) 预处理 
		if(in[L]==in[R]){
			for(int i=L;i<=R;i++) cnt[a[i]]++;
			ll mx=0;
			for(int i=L;i<=R;i++) mx=max(mx,(ll)cnt[a[i]]*old[a[i]]);
			ans[I]=mx;
			for(int i=L;i<=R;i++) cnt[a[i]]--;
			continue;
		} // L,R 所在快相同，暴力计算 
		while(r<R) Add(a[++r],res); // 扩展 R 
		int ll=l;
		tmp=res; 
		while(L<ll) Add(a[--ll],tmp); // 扩展 L 
		ans[I]=tmp;
		while(ll<l) Del(a[ll++]); // 还原 L 
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}