题目描述

给定n个整数，这n个整数已经从小到大排好序。

现在有m个询问，每次询问区间[a, b]内，最频繁出现的数字，出现了几次。

输入

输入n, m

接下来一行，输入n个整数vi

然后m行，每行输入一个区间a, b

输出

对于每个询问，输出最频繁出现的数字，出现了几次

样例输入

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10

样例输出

1
4
3

提示

【样例说明】

[2, 3]里最频繁出现数字是-1和1，都出现了1次
[1, 10]里最频繁出现数字是1，出现了4次
[5, 10]里最频繁出现数字是10，出现了3次

【数据规模和约定】
1<=n, m<=100000 -100000<=vi<=100000

思路

因为序列是有序的,可以用T[i]表示,在第i的数之前(包括i)中,与i相同的值的个数
用RMQ的方式处理出区间最大值
每次统计时,先统计出一段以T[i]=1为起点的最大值,在与T[i]前的数取一个最大值即可

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,l,r,a[100005],t[100005],last[100005],f[100005][18];

int getf(int l,int r){
    int len=r-l+1;
    int tmp=log(len)/log(2);
    int ret;
    if (t[l]==1){
        ret=max(f[l][tmp],f[r-(1<<tmp)+1][tmp]);
    }else{
        int la=last[l];
        if (la>=r) ret=r-l+1;
        else{
            ret=max(getf(la+1,r),la-l+1);
        }
    }
    return ret;
}

void initf(){
    for (int i=1;i<=n;++i) f[i][0]=t[i];
    int tt=log(n)/log(2);
    for (int j=1;j<=tt;++j){
        for (int i=1;i<=n-(1<<j)+1;++i){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for (int i=1;i<=n;++i){
        if (a[i]!=a[i-1]) t[i]=1;
        else t[i]=t[i-1]+1;
    }
    last[n]=n;
    for (int i=n-1;i>=1;--i){
        if (a[i]!=a[i+1]) last[i]=i;
        else last[i]=last[i+1];
    }
    initf();
    for (int i=1;i<=m;++i){
        scanf("%d %d",&l,&r);
        printf("%d\n",getf(l,r));
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/67/