本文主要是介绍UVA 11235 - Frequent values(RMQ)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 11235 - Frequent values
题目链接
题意：给定一个升序数列，每次询问一个区间[l, r]，求出其中相同数字最大的个数
思路：RMQ，由于是升序，所以数字大小相同的必然连在一块，先预处理出一共有多少段，每段包含多少个数字，和原数组中每个位置对应哪一段，最左边位置和最右边位置，然后每次询问的时候，可以把询问[L, R]的时候可以分成三段:
1、L到r[L]为一段，个数为R[L] - L + 1
2、l[R]到R为一段，个数为R - l[R] + 1
3、中间所有为一段，这一段就可以用RMQ求解，以个数为值
最后三段中个数较大的就是答案了
注意判断所选[L,R]只有1段和2段的情况
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 100005;int n, q, a[N], l[N], r[N], num[N], cnt[N], v, rmq[N][20];void init() {v = 0; int count, pre;scanf("%d", &q);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);if (!i || a[i] != a[i - 1]) {pre = i;if (i)cnt[v++] = count;count = 0;}count++;num[i] = v;l[i] = pre;}cnt[v++] = count;for (int i = n - 1; i >= 0; i--) {if (i == n - 1 || a[i] != a[i + 1]) {pre = i;}r[i] = pre;}
}void Build_RMQ(int* a, int n) {for (int i = 0; i < n; i++) rmq[i][0] = a[i];for (int j = 1; (1<<j) <= n; j++) {for (int i = 0; i + (1<<j) - 1 < n; i++) {rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j - 1))][j - 1]);}}
}int Query(int l, int r) {if (l > r) return 0;int k = 0;while ((1<<(k + 1)) <= r - l + 1) k++;return max(rmq[l][k], rmq[r - (1<<k) + 1][k]);
}void solve() {Build_RMQ(cnt, v);int L, R;while (q--) {scanf("%d%d", &L, &R);L--; R--;if (num[L] == num[R]) printf("%d\n", R - L + 1);else printf("%d\n", max(Query(num[L] + 1, num[R] - 1), max(r[L] - L + 1, R - l[R] + 1)));}
}int main() {while (~scanf("%d", &n) && n) {init();solve();}return 0;
}这篇关于UVA 11235 - Frequent values(RMQ)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
