AT1219 历史研究

一道回滚莫队的例题。
莫队算法能够解决很多类似于求和的询问问题。但是对于求最值的询问它无能为力。这是因为莫队需要一个区间既能够拓展又能够收缩。
对于求最值类的问题，它只能够拓展，不能够收缩。
这时候我们可以使用一种被称为「回滚莫队」的算法。
具体来说，对于每个块内的询问，我们都分成两部分来处理。一部分是将右端点推进，另一部分则是将左端点推进。对于每一个询问，我们在求得它向右端点推进的值以后，暴力统计上左端点对它的贡献即可。
请注意回滚莫队不能奇偶分块。结合回滚莫队的性质可以很容易理解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
int BLOCK,NUM;
int bl[100005],lb[100005],rb[100005];
struct Query{
	int l;
	int r;
	int id;
	inline bool operator<(const Query &B)const{
		return (bl[l]^bl[B.l])?(bl[l]<bl[B.l]):(r<B.r);
	}
}q[100005];
int n,m,a[100005],cnt1[100005],cnt2[100005],loc[100005],typ[100005];
long long ans[100005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=std::sqrt(n);
	NUM=std::ceil((double)n/BLOCK);
	for(int i=1;i<=NUM;++i){
		lb[i]=BLOCK*(i-1)+1;
		rb[i]=BLOCK*i;
		for(int j=lb[i];j<=rb[i];++j){
			bl[j]=i;
		}
	}
	rb[NUM]=n;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		loc[i]=a[i];
	}
	std::sort(loc+1,loc+1+n);
	int tot=std::unique(loc+1,loc+1+n)-loc-1;
	for(int i=1;i<=n;++i){
		typ[i]=std::lower_bound(loc+1,loc+1+tot,a[i])-loc;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	std::sort(q+1,q+1+m);
	int p=1;
	for(int i=0;i<=NUM;++i){
		int l=rb[i]+1,r=rb[i];
		long long nw=0;
		for(int j=1;j<=n;++j){
			cnt1[j]=0;
		}
		for(;bl[q[p].l]==i;++p){
			int ql=q[p].l,qr=q[p].r;
			long long tmp=0;
			if(bl[ql]==bl[qr]){
				for(int j=ql;j<=qr;++j){
					cnt2[typ[j]]=0;
				}
				for(int j=ql;j<=qr;++j){
					++cnt2[typ[j]];
					tmp=std::max(tmp,1ll*cnt2[typ[j]]*a[j]);
				}
				ans[q[p].id]=tmp;
				continue;
			}
			while(r<qr){
				++r;
				++cnt1[typ[r]];
				nw=std::max(nw,1ll*cnt1[typ[r]]*a[r]);
			}
			tmp=nw;
			while(l>ql){
				--l;
				++cnt1[typ[l]];
				nw=std::max(nw,1ll*cnt1[typ[l]]*a[l]);
			}
			ans[q[p].id]=nw;
			while(l<rb[i]+1){
				--cnt1[typ[l]];
				++l;
			}
			nw=tmp;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld\n",ans[i]);
	}
}

int main(){
	init();
	return 0;
}