E 仓鼠与珂朵莉（WHU新生赛）

题目链接：https://ac.nowcoder.com/acm/contest/8925/E

题意：定义一个区间的重要程度：max（k*k在区间中的个数）（k为区间中的数），有m个查询操作，求区间[l,r]间的重要程度。（强制在线）

思路：本题是“暴力美学”的杰出代表，使用分块可以O(n√n)内完成。首先由于区间中的数在[0,1e9]的范围内，所以先用离散化。要使用分块，那就要求出整大块的答案，左右两边不成块的数在O(√n)内处理即可。所以我们需求出第i块到第j块的重要程度f[i][j]，暴力枚举左起的i，然后向右处理出f[i][j]即可，复杂度为O(n√n)。至于如何处理零散数，可以维护h[i][j]表示第i块数j的个数，枚举零散数并加上整块中该数的个数从而来维护区间重要程度。但是这么做的话，每次把整块的数的的个数加起来时需要O(√n)的复杂度，时间显然爆表。因此，用前缀和维护h[i][j]即可。

总步骤：离散化---->分块---->预处理f[i][j]和前缀和sum[i][j]---->进行计算操作（整块、零散）

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL long long
LL n,m,a[100100],b[100100],cnt;
LL l[320],r[320],blo,num,bel[100100];
LL vis[100100],sum[320][100100],f[320][320];
void lisan()
{
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    return;
}
void fk()
{
    blo=sqrt(n);
    num=n/blo;
    if (n%blo) num++;
    for(int i=1;i<=num;i++) {l[i]=(i-1)*blo+1; r[i]=i*blo;}
    r[num]=n;
    for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
    return;
}
void init()
{
    LL now;
    for(int i=1;i<=num;i++)
    {
        now=0;
        for(int j=i;j<=num;j++)
        {
            for(int k=l[j];k<=r[j];k++)
            {
                vis[a[k]]++;
                now=max(now,vis[a[k]]*b[a[k]]);
            }
            f[i][j]=now;
        }
        for(int j=l[i];j<=n;j++) vis[a[j]]--;
        for(int j=l[i];j<=r[i];j++) sum[i][a[j]]++;
    }
    for(int i=1;i<=num;i++)
    for(int j=1;j<=cnt;j++)
    sum[i][j]+=sum[i-1][j];
    return;
}
LL calc(LL ll,LL rr)
{
    LL nl,nr,ret;
    if (l[bel[ll]]==ll) nl=bel[ll];
    else nl=bel[ll]+1;
    if (r[bel[rr]]==rr) nr=bel[rr];
    else nr=bel[rr]-1;
    ret=0;
    if (nl!=bel[ll])
    {
        for(int i=ll;i<=r[bel[ll]];i++)
        {
            vis[a[i]]++;
            ret=max(ret,(vis[a[i]]+sum[nr][a[i]]-sum[nl-1][a[i]])*b[a[i]]);
        }
    }
    if (nr!=bel[rr])
    {
        for(int i=l[bel[rr]];i<=rr;i++)
        {
            vis[a[i]]++;
            ret=max(ret,(vis[a[i]]+sum[nr][a[i]]-sum[nl-1][a[i]])*b[a[i]]);
        }
    }
    if (nl<=nr) ret=max(ret,f[nl][nr]);
    if (nl!=bel[ll])
    for(int i=ll;i<=r[bel[ll]];i++) vis[a[i]]--;
    if (nr!=bel[rr])
    for(int i=l[bel[rr]];i<=rr;i++) vis[a[i]]--;
    return ret;
}
int main()
{
    LL ans=0,ll,rr;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) {scanf("%lld",&a[i]); b[i]=a[i];}
    lisan();
    fk();
    init();
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&ll,&rr);
        ll=(ll^ans)%n+1;
        rr=(rr^ans)%n+1;
        if (ll>rr) ll^=rr^=ll^=rr;
        ans=calc(ll,rr);
        printf("%lld
",ans);
    }
    return 0;
}

E 仓鼠与珂朵莉（WHU新生赛）

相关推荐