文章目录[隐藏]
洛谷：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
|
1 2 3 4 5 |
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 |
Sample Output
|
1 |
1 4 3 |
解析及代码
暴力：
我们考虑暴力解法，根据题意模拟即可，复杂度\(O(qn^2)\)（不计算Map复杂度）
|
1 2 3 4 5 6 7 8 9 |
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)\)的算法。可以通过本题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#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]的最大值的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#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; } |
