题目描述
IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间，大约每天发生一件。
事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。
JOI教授决定用如下的方法分析这些日记：
1. 选择日记中连续的一些天作为分析的时间段
2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3. 计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
输入
第一行两个空格分隔的整数N和Q，表示日记一共记录了N天，询问有Q次。
接下来一行N个空格分隔的整数X1...XN，Xi表示第i天发生的事件的种类
接下来Q行，第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi，表示第i次询问的区间为[Ai,Bi]。
输出
输出Q行，第i行(1<=i<=Q)一个整数，表示第i次询问的最大重要度
样例输入
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
样例输出
9
8
8
16
16
题解
分块
本题卡$O(nsqrt nlog n)$，所以不能使用莫队（亲测被卡出*），使用分块的话也不能带log。
考虑到一段区间内的答案，只有可能是整块的答案，或者是块外出现的数在这个区间内的答案。证明很简单，略了。
对于整块的答案，我们可以开一个桶，然后用$O(nsqrt n)$的时间预处理。
对于区间外的答案，除了暴力扫出块外的数的出现次数，还要知道块内某数出现的次数。所以还需要再预处理出前i块中某数的出现次数，然后前缀相减即可。
需要一个离散化，但是不要忘记在求答案时反离散化回来。
时间复杂度$O(nsqrt n)$
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
typedef long long ll;
int a[N] , val[N] , cnt[N] , num[410][N];
ll ans[410][410];
int main()
{
int n , m , si , i , j , k , x , y;
ll maxn;
scanf("%d%d" , &n , &m) , si = (int)sqrt(n);
for(i = 0 ; i < n ; i ++ ) scanf("%d" , &a[i]) , val[i] = a[i];
sort(val , val + n);
for(i = 0 ; i < n ; i ++ ) a[i] = lower_bound(val , val + n , a[i]) - val;
for(i = 0 ; i <= (n - 1) / si ; i ++ )
{
for(j = i * si ; j < (i + 1) * si && j < n ; j ++ ) cnt[a[j]] ++ ;
for(j = 0 ; j < n ; j ++ ) num[i][j] = cnt[j];
}
for(i = 0 ; i <= (n - 1) / si ; i ++ )
{
memset(cnt , 0 , sizeof(cnt)) , maxn = 0;
for(j = i ; j <= (n - 1) / si ; j ++ )
{
for(k = j * si ; k < (j + 1) * si && k < n ; k ++ ) cnt[a[k]] ++ , maxn = max(maxn , (ll)cnt[a[k]] * val[a[k]]);
ans[i][j] = maxn;
}
}
memset(cnt , 0 , sizeof(cnt));
while(m -- )
{
scanf("%d%d" , &x , &y) , x -- , y -- ;
if(y / si - x / si < 2)
{
maxn = 0;
for(i = x ; i <= y ; i ++ ) cnt[a[i]] ++ , maxn = max(maxn , (ll)cnt[a[i]] * val[a[i]]);
for(i = x ; i <= y ; i ++ ) cnt[a[i]] -- ;
}
else
{
maxn = ans[x / si + 1][y / si - 1];
for(i = x ; i < (x / si + 1) * si ; i ++ ) cnt[a[i]] ++ , maxn = max(maxn , (ll)(cnt[a[i]] + num[y / si - 1][a[i]] - num[x / si][a[i]]) * val[a[i]]);
for(i = y / si * si ; i <= y ; i ++ ) cnt[a[i]] ++ , maxn = max(maxn , (ll)(cnt[a[i]] + num[y / si - 1][a[i]] - num[x / si][a[i]]) * val[a[i]]);
for(i = x ; i < (x / si + 1) * si ; i ++ ) cnt[a[i]] -- ;
for(i = y / si * si ; i <= y ; i ++ ) cnt[a[i]] -- ;
}
printf("%lld
" , maxn);
}
return 0;
}