洛谷：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;
}
文章评论