Wrong Answer on #5

AT 提交记录

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define bl(x) ((x-1)/B+1)
#define fr(x) ((x-1)*B+1)
#define bk(x) (fr(x+1)-1)
using namespace std;

int n,m,q,l,r;
long long an[100007];
int a[100007],b[100007],c[100007];
struct query{
	int x,y,id;
}qu[100007];
vector<query> vs[507];
bool cmp(query a,query b){
	return a.y<b.y;
}
int be[100007];
int B;
long long ans;
void add(int x){
	be[b[x]]++,ans=max(ans,1ll*a[x]*be[b[x]]);
}
signed main(){
	scanf("%d%d",&n,&q);
	B=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),c[i]=a[i];
	sort(c+1,c+n+1);
	m=unique(c+1,c+n+1)-c;
	for(int i=1;i<=n;i++){
		b[i]=lower_bound(c+1,c+m+1,a[i])-c;
		//printf("%d ",b[i]);
	}
	//printf("\n");
	for(int i=1;i<=q;i++){
		scanf("%d%d",&qu[i].x,&qu[i].y),qu[i].id=i;
		if(bl(qu[i].x)<bl(qu[i].y)) vs[bl(qu[i].x)].push_back(qu[i]);
		else{
			//printf("Brute Force on #%d\n",i);
			for(int j=qu[i].x;j<=qu[i].y;j++) add(j);
			an[qu[i].id]=ans;
			for(int j=qu[i].x;j<=qu[i].y;j++) be[b[j]]--;
			ans=0;
		}
	}
	for(int i=1;i<bl(n);i++){
		sort(vs[i].begin(),vs[i].end(),cmp);
	}
	for(int i=1;i<bl(n);i++){
		for(int j=0;j<=n;j++) be[j]=0;
		r=bk(i),ans=0;
		for(int j=0;j<vs[i].size();j++){
			query qq=vs[i][j];
			l=bk(i)+1; 
			while(r<qq.y) add(++r);
			long long now=ans;
			while(l>qq.x) add(--l);
			an[qq.id]=ans;
			ans=now;
			while(l<bk(i)+1) be[b[l++]]--;
		}
	}
	for(int i=1;i<=q;i++) printf("%lld\n",an[i]);
	return 0;
}