BZOJ-4241: 历史研究

[文章目录]

Description

日记中记录了连续N天发生的时间,大约每天发生一件。事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。JOI教授决定用如下的方法分析这些日记:
1. 选择日记中连续的一些天作为分析的时间段
2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3. 计算出所有事件种类的重要度,输出其中的最大值
现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。n,q<=10^5

和上一题一样,处理整块的答案,每次询问用零散部分更新答案。

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100100
typedef long long ll;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
    return x;
}
int n,m,bl,a[N],b[N],tot,z[700];
ll c[N];
int f[320][320],g[N][320],t[N];
int main()
{
    n=read(); m=read();
    int i; bl=(int)sqrt(n)+1;
    for(i=0;i<n;++i) b[i]=a[i]=read();
    sort(b,b+n); c[tot++]=b[0];
    for(i=1;i<n;++i) if(b[i]!=b[i-1]) c[tot++]=b[i];
    for(i=0;i<n;++i) a[i]=lower_bound(c,c+tot,a[i])-c;
    int l,r,now=0;
    for(l=0;l<n;l+=bl)
    {
        memset(t,0,sizeof t);
        for(r=l+bl-1,i=l;i<n;++i)
        {
            t[a[i]]++;
            if(c[a[i]]*t[a[i]]>c[now]*t[now]) now=a[i];
            if(i==r) f[l/bl][r/bl]=now,r+=bl;
        }
    }
    memset(t,0,sizeof t);
    for(l=0,r=bl-1;l<n;++l)
    {
        t[a[l]]++;
        if(l==r) for(r+=bl,i=0;i<tot;++i) g[i][l/bl]=t[i];
    }
    memset(t,0,sizeof t);
    int L,R,top;
    while(m--)
    {
        l=read()-1; r=read()-1;
        if(r-l+1<=bl*2)
        {
            for(now=0,i=l;i<=r;++i)
            {
                t[a[i]]++;
                if(c[a[i]]*t[a[i]]>c[now]*t[now]) now=a[i];
            }
            printf("%lld\n",c[now]*t[now]);
            for(i=l;i<=r;++i) t[a[i]]=0;
        }
        else
        {
            L= l%bl==0 ? l/bl : l/bl+1;
            R= r%bl==bl-1 ? r/bl : r/bl-1;
            for(top=0,i=l;i%bl!=0;++i)
            {
                if(!t[a[i]]) z[++top]=a[i];
                t[a[i]]++;
            }
            for(i=r;i%bl!=bl-1;--i)
            {
                if(!t[a[i]]) z[++top]=a[i];
                t[a[i]]++;
            }
            if(!t[f[L][R]]) z[++top]=f[L][R];
            for(now=0,i=1;i<=top;++i)
            {
                t[z[i]]+=g[z[i]][R]-g[z[i]][L-1];
                if(c[z[i]]*t[z[i]]>c[now]*t[now]) now=z[i];
            }
            printf("%lld\n",c[now]*t[now]);
            for(i=1;i<=top;++i) t[z[i]]=0;
        }
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注