洛谷：https://www.luogu.org/problemnew/show/U50167

Description

给定一个非降序的由 n 个整数构成的序列以及 q 个由整数i 和 j 构成的询问。对于每一个询问，输出在 a[i],a[i+1], … ,a[j-1],a[j]里面出现次数最多的那个(些)整数出现的次数。

Input

第一行包含两个整数， n 和 q。第二行包括 n 个整数 a[1],a[2], … ,a[n]，由空格分开。以下 q 行每一行包括一个询问，一个询问由两个整数 i 和 j 构成， i 和 j 指示询问索引的边界。 保证 i<=j。

Output

对于每一组询问，输出一行一个整数：在给定区间内出现次数最多的那个(些)整数出现的次数。

Sample Input

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

Sample Output

1 4 3

解析及代码

暴力：

我们考虑暴力解法，根据题意模拟即可，复杂度\(O(qn^2)\)（不计算Map复杂度）

void baoli() {
	for(int i = 1;i <= m;++i) {
		int l,r,ans = 0;
		map <int ,int > M;
		scanf("%d%d",&l,&r);
		for(int j = l;j <= r;++j) M[a[j]]++,ans = max(ans,M[a[j]]);
		printf("%d\n",ans);
	}
}

正解①：

考虑用ST表维护区间内每个数出现的次数。对于区间l,r，我们可以分为l ->a[l]最后出现的地方 和a[r]一开始出现的地方->r 以及 a[l]最后出现的地方+1到a[r]最开始出现的地方-1三个区间。

对于第一个和第二个区间。我们暴力查找，通过二分将我们需要的a[r]一开始出现的地方 及 a[l]最后出现的地方。倘若l仍然小于r我们在查找满区间（没有被l,r分割的区间），这样我们就得到了\(O(qlogn)\)的算法。可以通过本题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std; 

const int MAXN = 100005;

int a[MAXN];
int lg[MAXN];
int Max[MAXN][22];
int n,Num = 1,m; 

void Init() {
	lg[0] = -1;
	for(int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j <= 21;++j)	
		for(int i = 1;i + (1 << j) - 1 <= n;++i)	
			Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]);
}

int Query(int l,int r) {
	int k = lg[r - l + 1];
	return max(Max[l][k],Max[r - (1 << k) + 1][k]);
}

int main() {
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	scanf("%d%d",&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]) Num++;
		else Num = 1;
		Max[i][0] = Num; //到达每一个点时每一个数的最大出现次数 
	}
	Init();
	for(int i = 1;i <= m;++i) {
		int l,r;
		scanf("%d%d",&l,&r); //分段 分l->a[l]最后出现的位置 a[r]一开始出现的位置->r  和  完整的区间进行ST查询 
		int pos2 = lower_bound(a + 1,a + 1 + n,a[r]) - a; // 返回当前a[r]一开始出现的位置
		if(a[pos2] != a[r]) pos2++; 
		if(pos2 < l) pos2 = l; //特判一下，如果a[r]一开始出现的位置比l小，我们是不可取pos2的 
		int Ans = r - pos2 + 1; //一开始定义Ans为a[r]出现的次数 
		r = pos2 - 1; //找下一个完整区间的数 
		if(l > r) { //如果l比r大了，那么我们找完了所有区间 
			printf("%d\n",Ans);
			continue;
		}
		int pos1 = upper_bound(a + 1,a + 1 + n,a[l]) - a; //返回当前a[l]最后出现的位置
		if(a[pos1] != a[l]) pos1--; 
		Ans = max(Ans,pos1 - l + 1); //将两个单独的区间取max 
		//cout << pos1 << " " << pos2 << endl << endl;
		l = pos1 + 1;
		if(l > r) { //如果l比r还大，那么我们已经找完了所有区间 
			printf("%d\n",Ans);
			continue;
		}
		Ans = max(Ans,Query(l,r));  //否则我们寻找完整的区间进行ST 
		printf("%d\n",Ans);
	}
	return 0;
}

正解②：

在维护到达每一个点时每一个数的最大出现次数 时，我们可以倒序枚举，这样就不用管开头的区间了，因为保证了单调递增，这样我们RMQ查询时默认肯定会到达a[l]的最大值的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std; 

const int MAXN = 100005;

int a[MAXN];
int lg[MAXN];
int Max[MAXN][22];
int n,Num = 1,m; 

void Init() {
	lg[0] = -1;
	for(int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j <= 21;++j)	
		for(int i = 1;i + (1 << j) - 1 <= n;++i)	
			Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]);
}

int Query(int l,int r) {
	int k = lg[r - l + 1];
	return max(Max[l][k],Max[r - (1 << k) + 1][k]);
}

int main() {
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) scanf("%d",a + i);
	for(int i = n;i >= 1;--i) {
		if(a[i] == a[i + 1]) Num++;
		else Num = 1;
		Max[i][0] = Num; //到达每一个点时每一个数的最大出现次数 
	}
	Init();
	for(int i = 1;i <= m;++i) {
		int l,r;
		scanf("%d%d",&l,&r); //分段 分l->a[l]最后出现的位置 a[r]一开始出现的位置->r  和  完整的区间进行ST查询 
		int pos2 = lower_bound(a + 1,a + 1 + n,a[r]) - a; // 返回当前a[r]一开始出现的位置
		if(pos2 < l) pos2 = l; //特判一下，如果a[r]一开始出现的位置比l小，我们是不可取pos2的 
		//if(i == m) cout << l << " " << r << " " << pos2 << endl;
		int Ans = r - pos2 + 1; //一开始定义Ans为a[r]出现的次数 
		r = pos2 - 1; //找下一个完整区间的数 
		if(l > r) { //如果l比r大了，那么我们找完了所有区间 
			printf("%d\n",Ans);
			continue;
		}
		Ans = max(Ans,Query(l,r));  //否则我们寻找完整的区间进行ST 
		printf("%d\n",Ans);
	}
	return 0;
}