题目描述

每次考试结束，老师总要把所有的同学的成绩进行排序，这还不够，老师总关心获得哪个分数的学生人数是最多的，请帮助老师完成这个任务。

输入格式

第一行包含两个整数n和m，分别代表n个同学，后续有m个询问。 第二行包含n个同学的成绩，这n个同学的成绩是一个整数，而且已经是从小到大排好序的。 接下来m行，每行包含两个整数l和r，表示老师需要了解第l个同学到第r个同学间（包含第l和第r个同学）得到同分的最多人数，针对每个询问，请输出最多人数。

输出格式

每行一个整数，表示对应区间的得到同分的最多人数

输入样例

10 3

2 2 6 6 6 6 8 10 10 10

2 3

1 10

5 10

输出样例

1

4

3

My Code

#include<bits/stdc++.h>
using namespace std;
int n,m,Log[100001],f[100001][31];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline int RMQ(int x,int y,int l)
{
	return max(f[x][l],f[y-(1<<l)+1][l]);
}
int main()
{
 //	freopen(".in","r",stdin);
 //	freopen(".out","w",stdout);
 	n=read(),m=read();
 	int la=114514;
	for(int i=1;i<=n;i++)
	{
		int x=read();
		if(x==la)f[i][0]=f[i-1][0]+1;
		else f[i][0]=1;
		la=x;
	} 
	Log[1]=0;
	for(int i=2;i<=n;i++)Log[i]=Log[i/2]+1;
	for(int j=1;j<=Log[n];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]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		int l=Log[y-x+1];
		int maxx=RMQ(x,y,l);
		if(f[x][0]==1)printf("%d\n",maxx);
		else
		{
			if(f[x+maxx-f[x][0]][0]==maxx)printf("%d\n",max((maxx-f[x][0]+1),RMQ(x+maxx-f[x][0]+1,y,Log[y-(x+maxx-f[x][0])])));
			else printf("%d\n",maxx);
		}
	}
 	return 0;
}

ST表

自己的数据都没问题，样例也过了，交上去0分

思路大致是：

构造一个序列，例如样例构造成：1 2 1 2 3 4 1 1 2 3

然后针对每一次询问，先查区间最大值，然后看区间开头是不是1，如果是的话答案就一定是最大值（这里不是说一定和最大值是一段的，即使不是一段的，最大值也有一段完整的序列），如果不是就判断最大值与区间开头是不是一段的：

是的话比较这一段的长度和后面的区间最大值

不是的话直接输出最大值