本文主要是介绍UVA 11235 - Frequent values (RMQ的基础应用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一个非降序排列的整数数组a[1], a[2], ...... , a[n]，给出一系列询问（i, j），回答a[i], a[i+1], ...... , a[j]中出现最多的值所出现的次数。
思路：典型的RMQ应用，第一次仿着写，将数组游程编码，value[i]和cnt[i]分别表示第i段的数值和出现次数，num[p], left[p], right[p]分别表示位置p所在段的编号和左右端点的位置。则查询（L， R）的结果为以下三部分的最大值：从L到L所在段的结束的个数（right[L]-L+1），从R所在段的开始到R处的个数（R-left[R]+1），中间从num[L]+1到num[R]-1段的count的最大值。如果L和R在同一段，则答案就是R-L+1。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 100010;int dp[MAXN][30],value[MAXN],cnt[MAXN],num[MAXN],left[MAXN],right[MAXN];int RMQ(int l,int r){if (r < l)return 0;int k = log(1.0*r-l+1) / log(2.0);return max(dp[l][k],dp[r-(1<<k)+1][k]);
}int main(){int x,n,m,q;while (scanf("%d",&n) != EOF && n){scanf("%d",&q);memset(right,0,sizeof(right));m = 0;for (int i = 1; i <= n; i++){scanf("%d",&x);if (!m || value[m] != x){value[++m] = x;cnt[m] = 1;}else cnt[m]++;num[i] = m;}cnt[m+1] = n;int k = 1,temleft = 1,temright = cnt[1];for (int i = 1; i <= m; i++){for (int j = 1; j <= cnt[i]; j++){left[k] = temleft;right[k++] = temright;}temleft += cnt[i];temright += cnt[i+1];}for (int i = 1; i <= m; i++)dp[i][0] = cnt[i]; // 第i段for (int j = 1; (1<<j) <= m; j++)for (int i = 1; i + (1<<j)-1 <= m; i++)dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);int l,r;while (q--){scanf("%d %d",&l,&r);if (left[l] == left[r])printf("%d\n",r-l+1);else printf("%d\n",max(max(right[l]-l+1,r-left[r]+1),RMQ(num[l]+1,num[r]-1)));}}return 0;
}这篇关于UVA 11235 - Frequent values (RMQ的基础应用)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
