zcmimi's blog
avatar
zc
2020-07-18 11:27:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
const int N=100011;
int n,m,blk,nn,a[N],c[N],cnt[N],CNT[N];
typedef long long ll;
ll ans[N],mx;
struct node{
    int v,id;
    bool operator<(node t){return v<t.v;}
}b[N];
struct que{
    int l,r,id,pl,pr;
    bool operator<(que t){return pl!=t.pl?l<t.l:r<t.r;}
}q[N];
void cmax(ll&x,ll y){if(y>x)x=y;}
int main(){
    scanf("%d%d",&n,&m);blk=sqrt(n);
    for(int i=1;i<=n;++i)
        scanf("%d",c+i),
        b[i]=(node){c[i],i};
    std::sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)
        a[b[i].id]=nn+=b[i].v!=b[i-1].v;
    int l,r;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&l,&r),
        q[i]=(que){l,r,i,(l-1)/blk+1,(r-1)/blk+1};
    std::sort(q+1,q+m+1);
    int tot=(n-1)/blk+1;
    for(int now=1,i=1,R=blk;now<=tot;R+=blk,++now){
        if(R>n)R=n;
        l=R+1,r=R,mx=0;
        for(;q[i].pl==now;++i){
            if(q[i].pl==q[i].pr){
                for(int j=q[i].l;j<=q[i].r;++j)++CNT[a[j]];
                for(int j=q[i].l;j<=q[i].r;++j)
                    cmax(ans[q[i].id],1ll*CNT[a[j]]*c[j]);
                for(int j=q[i].l;j<=q[i].r;++j)--CNT[a[j]];
                continue;
            }
            while(r<q[i].r)
                cmax(mx,1ll*++cnt[a[++r]]*c[r]);
            ans[q[i].id]=mx;
            while(l>q[i].l)
                cmax(ans[q[i].id],1ll*++cnt[a[--l]]*c[l]);
            for(;l<=R;++l)--cnt[a[l]];
        }
        for(;r>=R;--r)--cnt[a[r]];
    }
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
}
LG 4137 Rmq Problem-mex
comment评论
Search
search