题目描述

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)

题目分析

区间带权众数 时间复杂度做法
预处理出每个数前缀块和 块和块之间的众数 即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,siz;
long long ans,f[400][400];
int sum[400][100010];
struct your
{
    long long val;
    int id;
}a[100010];
int c[100010],tot;
int cmp(your j,your k) { return j.val<k.val; }
int cmp2(your j,your k) { return j.id<k.id; }
int num[100010];
void init()
{
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        tot=tot+(a[i].val!=a[i-1].val),c[a[i].id-1]=tot;
    sort(a+1,a+n+1,cmp2);
    for(int i=0;i<n;i++) a[i]=a[i+1],sum[i/siz][c[i]]++;
    for(int i=0;i*siz<n;i++)
    {
        for(int j=1;j<=tot;j++) sum[i][j]+=sum[i-1][j];
        for(int j=i;j*siz<n;j++)
        {
            f[i][j]=f[i][j-1];
            for(int k=j*siz;k<j*siz+siz&&k<n;k++)
                num[c[k]]++,f[i][j]=max(f[i][j],(long long) num[c[k]]*a[k].val );
        }
        memset(num,0,sizeof num);
    }
}
void getans(int x,int y)
{
    ans=0;
    if(x/siz==y/siz)
    {
        for(int i=x;i<=y;i++)
            num[c[i]]++,ans=max(ans,(long long) num[c[i]]*a[i].val);
        for(int i=x;i<=y;i++) num[c[i]]=0;
        return ;
    }
    ans=f[x/siz+1][y/siz-1];
    for(int i=x;i<x/siz*siz+siz;i++) num[c[i]]=sum[y/siz-1][c[i]]-sum[x/siz][c[i]];
    for(int i=y/siz*siz;i<=y;i++) num[c[i]]=sum[y/siz-1][c[i]]-sum[x/siz][c[i]];
    for(int i=x;i<x/siz*siz+siz;i++) num[c[i]]++,ans=max(ans,(long long) num[c[i]]*a[i].val);
    for(int i=y/siz*siz;i<=y;i++) num[c[i]]++,ans=max(ans,(long long) num[c[i]]*a[i].val);
    for(int i=x;i<x/siz*siz+siz;i++) num[c[i]]=0;
    for(int i=y/siz*siz;i<=y;i++) num[c[i]]=0;
    return ; 
}
int main()
{   
    scanf("%d%d",&n,&m),siz=sqrt(1.0*n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i].val),a[i].id=i;
    init();
    for(int l,r,i=1;i<=m;i++)
        scanf("%d%d",&l,&r),getans(--l,--r),printf("%lld\n",ans);
    return 0;
}