BZOJ 4241: 历史研究

 

Time Limit: 80 Sec Memory Limit: 512 MB
Submit: 1628 Solved: 505
[Submit][Status][Discuss]
Description
IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间，大约每天发生一件。
事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。
JOI教授决定用如下的方法分析这些日记：
1. 选择日记中连续的一些天作为分析的时间段
2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3. 计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

Input
第一行两个空格分隔的整数N和Q，表示日记一共记录了N天，询问有Q次。
接下来一行N个空格分隔的整数X1…XN，Xi表示第i天发生的事件的种类
接下来Q行，第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi，表示第i次询问的区间为[Ai,Bi]。

Output
输出Q行，第i行(1<=i<=Q)一个整数，表示第i次询问的最大重要度

Sample Input
5 5

9 8 7 8 9

1 2

3 4

4 4

1 4

2 4
Sample Output
9

8

8

16

16
HINT

1<=N<=10^5

1<=Q<=10^5

1<=Xi<=10^9 (1<=i<=N)

解题思路

分块大法好！！cnt[i][j] 表示i这个块到最后中j出现的次数，f[i][j] 表示i块到j的最大值。然后每次询问时处理一下边角，就是x到r[x]与l[y]到y的最大值，与f[bl[x]+1][y] 取max即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> 
#include<algorithm>
#define LL long long

using namespace std;
const int MAXN = 100005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,q,a[MAXN],siz,bl[MAXN],l[MAXN],r[MAXN];
int cpy[MAXN],tot,cnt[333][MAXN];
int stk[MAXN],top,num[MAXN];
LL now,f[333][MAXN],ans,k[MAXN];

int main(){
    scanf("%d%d",&n,&q);siz=sqrt(n);
    tot=n/siz;if(n%siz) tot++;
    for(register int i=1;i<=n;i++) {
        a[i]=rd();
        bl[i]=(i-1)/siz+1;
        cpy[i]=a[i];
    }
    for(register int i=1;i<=tot;i++){
        l[i]=(i-1)*siz+1;
        r[i]=i*siz;
    }
    r[tot]=n;
    sort(cpy+1,cpy+1+n);
    int u=unique(cpy+1,cpy+1+n)-cpy-1;
    for(register int i=1;i<=n;i++) a[i]=lower_bound(cpy+1,cpy+1+u,a[i])-cpy;
    for(register int i=1;i<=tot;i++){
        now=0;
        for(register int j=l[i];j<=n;j++)
            cnt[i][a[j]]++,now=max(now,(LL)cnt[i][a[j]]*cpy[a[j]]),f[i][j]=now;
    }
//  for(register int i=1;i<=num;i++)
//      for(register int j=1;j<=n;j++){
//          cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
//      }
    for(register int i=1;i<=q;i++){
        int x=rd(),y=rd();
//      cout<<x<<" "<<y<<endl;
        ans=f[bl[x]+1][y];top=0;
        for(register int j=l[bl[y]];j<=y;j++){
            num[a[j]]++;
            stk[++top]=a[j];
        }   
        for(register int j=x;j<=r[bl[x]];j++) {
            num[a[j]]++;
            ans=max(ans,(LL)cpy[a[j]]*(cnt[bl[x]+1][a[j]]-cnt[bl[y]][a[j]]+num[a[j]]));
            stk[++top]=a[j];
        }
        printf("%lld\n",ans);
        for(register int j=1;j<=top;j++)
            num[stk[j]]=0;
    }   
    return 0;
}