[文章目录]
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;
}