AtCoder提交记录

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500005;

ll n,m,a[MAXN],bl,d[MAXN],cnt[MAXN],ans[MAXN],tot,backtot; 

struct node{
	int l,r,p;
}q[MAXN];

bool operator<(const node &a,const node &b){
	return a.l/bl^b.l/bl ? a.l<b.l : a.r<b.r;
}

void Add(ll x){
	tot=max(tot,++cnt[a[x]]*d[a[x]]);
}

int main(){
//	freopen("historical.in","r",stdin);
//	freopen("historical.out","w",stdout);
	scanf("%lld%lld",&n,&m);bl=(ll)sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&d[i]),a[i]=d[i];
	sort(d+1,d+n+1);
	int len=unique(d+1,d+n+1)-(d+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(d+1,d+len+1,a[i])-d;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&q[i].l,&q[i].r),q[i].p=i;
		if(q[i].l/bl==q[i].r/bl){
			for(int j=q[i].l;j<=q[i].r;j++) Add(j);
			ans[q[i].p]=tot,tot=0;
			for(int j=q[i].r;j>=q[i].l;j--) cnt[a[j]]--; //
			q[i].l=q[i].r=n+bl;
		}
	}
	sort(q+1,q+m+1);
	for(int i=1,curl=bl,curr=bl-1,bi=1;q[i].l<=n&&i<=m;i++){
		int L=q[i].l,R=q[i].r;
		if(bi^L/bl){
			bi=L/bl;curl=bl*bi+bl;curr=curl-1;backtot=tot=0; //
			memset(cnt,0,sizeof cnt);
		}
		while(curr<R) Add(++curr);
		backtot=tot;
		while(curl>L) Add(--curl);
		ans[q[i].p]=tot;
		while(curl<bl*bi+bl) cnt[a[curl++]]--; //
		tot=backtot;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}