C114 回滚莫队 歴史の研究

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m,B,block[N];
LL a[N],lsh[N],ln,ans[N],cnt[N],tcnt[N],res,last;
struct Qnode{int l,r,id;} q[N];
bool cmp(Qnode n1, Qnode n2) { return block[n1.l]!=block[n2.l] ? (n1.l<n2.l) : (n1.r<n2.r); }

void add(int x)
{
    ++cnt[x];
    res=max(res,cnt[x]*lsh[x]);
}
LL calc(int l,int r)
{
    LL mx=0;
    for(int i=l;i<=r;i++)tcnt[a[i]]=0;
    for(int i=l;i<=r;i++)
    {
        ++tcnt[a[i]];
        mx=max(mx,tcnt[a[i]]*lsh[a[i]]);
    }
    return mx;
}

int main()
{
    scanf("%d%d",&n,&m);B=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),lsh[i]=a[i],block[i]=(i-1)/B+1;
    int bn=block[n];
    sort(lsh+1,lsh+n+1);ln=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+ln+1,a[i])-lsh;
    for(int i=1,l,r;i<=m;i++)scanf("%d%d",&l,&r),q[i]={l,r,i};
    sort(q+1,q+m+1,cmp);
    for(int bi=1,i=1;bi<=bn;bi++)
    {
        res=last=0;
        memset(cnt,0,sizeof(cnt));
        int br=min(B*bi,n),l=br+1,r=br;
        for(;block[q[i].l]==bi;i++)
        {
            if(block[q[i].l]==block[q[i].r])
            {
                ans[q[i].id]=calc(q[i].l,q[i].r);
                continue;
            }
            
            while(r<q[i].r)add(a[++r]);  last=res;
            while(l>q[i].l)add(a[--l]);
            ans[q[i].id]=res;

            while(l<=br)--cnt[a[l++]];    res=last;
        }
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;
}