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
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
Sample Output
9
8
8
16
16
8
8
16
16
HINT
1<=N<=10^5
1<=Q<=10^5
1<=Xi<=10^9 (1<=i<=N)
正解：分块
解题报告：
这道题卡了我好久。。。数据恶心，差评。。。
w[i][j]表示第i块到第j块的答案（即题目要求的最大值）,cnt[i][j]表示前i块种类为j的数的个数前缀和。
显然这可以O（N^(3/2)）预处理。查询的时候整块的直接以整块答案为初值，然后考虑“边角余料”，加进num中统计，更新答案，具体看代码吧。
我开始WA了，因为有一个数组没开long long。。。之后一直TLE，我不知道一个评测80s的题目TLE几次是什么感觉。。。经过二分查错，我发现并没有问题。
最后迷之AC了，因为把一个不必要的long long开成了int就AC了。常数害死人。。。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
const int kk = ;
int n,m;
int belong[MAXN],L[MAXN],R[MAXN];
int num[MAXN];
int match[MAXN],Stack[MAXN],top;
LL w[kk][kk];
int cnt[kk][MAXN];//w[i][j]表示第i块到第j块的答案， cnt[i][j]表示前i块数字为j的个数
LL ans; struct node{
int val,id;
}a[MAXN]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline bool cmp(node q,node qq){ return q.val<qq.val; }
inline LL max(LL x,LL y){ if(x<y) return y; return x; } inline void work(){
n=getint(); m=getint(); int block=sqrt(n),kuai;
//int block=325; int kuai;
kuai=(n-)/block+;
for(int i=;i<=n;i++) a[i].val=getint(),a[i].id=i;
for(int i=;i<=n;i++) {
belong[i]=(i-)/block+;
if(!L[belong[i]]) L[belong[i]]=i;
R[belong[i]]=i;
}
sort(a+,a+n+,cmp); match[a[].id]=;
//用每个数字出现的第一个位置代替这个数字作为它的编号
for(int i=;i<=n;i++) {//构出从小到大的原来顺序的离散化结果
if(a[i].val==a[i-].val) match[a[i].id]=match[a[i-].id];
else match[a[i].id]=i;
}
for(int i=;i<=n;i++) cnt[belong[i]][match[i]]++;
for(int i=;i<=kuai;i++) for(int j=;j<=n;j++) cnt[i][j]+=cnt[i-][j];//构前缀和
for(int i=;i<=kuai;i++) {
memset(num,,sizeof(num)); ans=;
for(int now=L[i];now<=n;now++) {//按原先的顺序统计种类的个数
num[match[now]]++; ans=max(ans,(LL)num[match[now]]*a[match[now]].val);
if(now==R[belong[now]]) w[i][belong[now]]=ans;//已经到最后一个
}
}
memset(num,,sizeof(num));
int l,r;
for(int o=;o<=m;o++) {
l=getint(); r=getint(); ans=;
if(belong[l]==belong[r]) {
top=;
for(int i=l;i<=r;i++) { if(!num[match[i]]) Stack[++top]=match[i]; num[match[i]]++; ans=max(ans,(LL)num[match[i]]*a[match[i]].val); }
//我们记录一个处理过的种类，Stack保存需要清零的对象
while(top>) num[Stack[top--]]=;
}
else{
top=; if(belong[l]<belong[r]) ans=w[belong[l]+][belong[r]-];
//找到不完整的块中的出现的种类，然后统计完整的块中的出现的次数
for(int i=l;i<=R[belong[l]];i++) if(!num[match[i]]) num[match[i]]=cnt[belong[r]-][match[i]]-cnt[belong[l]][match[i]],Stack[++top]=match[i];
for(int i=L[belong[r]];i<=r;i++) if(!num[match[i]]) num[match[i]]=cnt[belong[r]-][match[i]]-cnt[belong[l]][match[i]],Stack[++top]=match[i];
for(int i=l;i<=R[belong[l]];i++) num[match[i]]++;
for(int i=L[belong[r]];i<=r;i++) num[match[i]]++;
while(top>) { ans=max(ans,(LL)num[Stack[top]]*a[Stack[top]].val); num[Stack[top--]]=;}//清零
}
printf("%lld\n",ans);
}
} int main()
{
work();
return ;
}