首先分成N^0.5块，然后答案显然是中间一整段的最大值，或者是两端零星的部分。
那么可以得到f[i][j]表示第i块到第j块的答案；然后就需要快速求出零星部分出现的次数，用一个前缀和s[i][j]表示在前i块中j出现的次数。
离散化搞一搞。
好像莫队也是可以的把。
AC代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define N 100005
#define M 335
using namespace std;
int n,m,cnt,c[N],num[N],g[N],s[M][N],l[M],r[M],blg[N];
ll f[M][M]; struct node{ int x,y; }a[N];
int read(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x;
}
bool cmp(node u,node v){ return u.x<v.x; }
int main(){
n=read(); int i,j,k,cas=read();
for (i=1; i<=n; i++){
a[i].x=read(); a[i].y=i;
}
sort(a+1,a+n+1,cmp);
for (i=1; i<=n; i++){
if (i==1 || a[i].x!=a[i-1].x) num[++cnt]=a[i].x;
c[a[i].y]=cnt;
}
m=(int)sqrt(n);
for (i=1; i<=m; i++){
l[i]=r[i-1]+1; r[i]=r[i-1]+m;
}
r[m]=n;
for (i=1; i<=m; i++)
for (j=l[i]; j<=r[i]; j++) blg[j]=i;
for (i=1; i<=m; i++){
memcpy(s[i],s[i-1],sizeof(s[i]));
for (j=l[i]; j<=r[i]; j++) s[i][c[j]]++;
}
for (i=1; i<=m; i++){
for (j=i; j<=m; j++){
f[i][j]=f[i][j-1];
for (k=l[j]; k<=r[j]; k++){
g[c[k]]++; f[i][j]=max(f[i][j],(ll)g[c[k]]*num[c[k]]);
}
}
for (j=1; j<=cnt; j++) g[j]=0;
}
int x,y,u,v; ll ans;
while (cas--){
x=read(); y=read(); u=blg[x]; v=blg[y];
if (u+1<v){
ans=f[u+1][v-1];
for (i=x; i<=r[u]; i++) g[c[i]]++;
for (i=y; i>=l[v]; i--) g[c[i]]++;
for (i=x; i<=r[u]; i++) ans=max(ans,(ll)(g[c[i]]+s[v-1][c[i]]-s[u][c[i]])*num[c[i]]);
for (i=y; i>=l[v]; i--) ans=max(ans,(ll)(g[c[i]]+s[v-1][c[i]]-s[u][c[i]])*num[c[i]]);
for (i=x; i<=r[u]; i++) g[c[i]]=0;
for (i=y; i>=l[v]; i--) g[c[i]]=0;
} else{
ans=0;
for (i=x; i<=y; i++){
g[c[i]]++; ans=max(ans,(ll)g[c[i]]*num[c[i]]);
}
for (i=x; i<=y; i++) g[c[i]]=0;
}
printf("%lld\n",ans);
}
return 0;
}
by lych
2016.3.25