RT，用最普通的回滚莫队写了，结果是：https://atcoder.jp/contests/joisc2014/submissions/29025763

感觉没啥问题，估计是细节的问题

#include<bits/stdc++.h>
using namespace std;

int n,m;

int a[100010],b[100010];

struct query
{
    int l,r,bl,id;
} q[100010];
bool cmp(query x,query y)
{
    return x.bl==y.bl?x.r<y.r:x.bl<y.bl;
}

int cnt[100010],cnt2[100010];

long long ans[100010];

int main()
{
    int block,all;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int tot=unique(b+1,b+n+1)-b-1;
    for(int i=1; i<=n; ++i)
    {
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    }
    block=all=sqrt(n);
    if(block*block!=n) ++all;
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].bl=q[i].l/block+1;
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1,j=1; j<=all; ++j)
    {
        memset(cnt,0,sizeof(cnt));
        int br=min(n,j*block),l=br+1,r=br;
        long long now=0;
        while(q[i].bl==j)
        {
            if(q[i].bl==q[i].r/block+1)
            {
                long long nowans=0;
                for(int k=q[i].l; k<=q[i].r; ++k)
                {
                    cnt2[a[k]]=0;
                }
                for(int k=q[i].l; k<=q[i].r; ++k)
                {
                    ++cnt2[a[k]];
                    nowans=max(nowans,1ll*b[a[k]]*cnt2[a[k]]);
                }
                ans[q[i].id]=nowans;
            }
            else
            {
                while(r<q[i].r)
                {
                    ++r;
                    ++cnt[a[r]];
                    now=max(now,1ll*b[a[r]]*cnt[a[r]]);
                }
                long long lastans=now;
                while(l>q[i].l)
                {
                    --l;
                    ++cnt[a[l]];
                    now=max(now,1ll*b[a[l]]*cnt[a[l]]);
                }
                ans[q[i].id]=now;
                now=lastans;
                while(l<=br)
                {
                    --cnt[a[l]];
                    ++l;
                }
            }
            ++i;
        }
    }
    for(int i=1; i<=m; ++i)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}