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
     
      #include
      
       #include
       
        #include
        
          #include
         
          #define LL long longusing 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<
          <<" "<
           
            <<" "<
            
             <