本文主要是介绍POJ 3368 RMQ--ST，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
e of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0Sample Output
1
4
3
先说一下题意 给出n个不减的数，询问Q次，求这n个数中连续的相等的数的最大数量
思路：将全数组转化成两个数组xu[ ]代表着数字的顺序-1 -1 1 1 1 1 3 10 10 10 就是
1 2 1 2 3 4 1 1 2 3
wei[ ]就是每一串相同字符的尾部index 2 2 6 6 6 6 7 10 10 10
还有一个 求区间 最大值的 RMQ
ans 如果要查询的wei[l]和wei[r] 相等的话直接就是l-r+1
其他情况 左边部分的l-r+1右边部分的RMQ求最大值
#include<iostream>
#include<stdio.h>
using namespace std;
int num[100009];
int xu[100009];
int wei[100009];
int dp[100009][30];
int n,q;
void ST(int n)
{for (int i = 1; i <= n; i++)dp[i][0] = xu[i];for (int j = 1; (1 << j) <= n; j++){for (int i = 1; i + (1 << j) - 1 <= n; i++){dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);}}
}
int RMQ(int l, int r)
{int k = 0;while ((1 << (k + 1)) <= r - l + 1) k++;return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int main()
{while(cin>>n){if(n==0)break;cin>>q;for(int i=1; i<=n; i++){scanf("%d",&num[i]);}xu[1]=1;for(int i=2; i<=n; i++){if(num[i]==num[i-1])xu[i]=xu[i-1]+1;else xu[i]=1;}wei[n]=n;for(int i=n-1; i>0; i--){if(num[i]==num[i+1])wei[i]=wei[i+1];elsewei[i]=i;}ST(n);for(int i=0; i<q; i++){int l,r;scanf("%d%d",&l,&r);if(wei[l]==wei[r])printf("%d\n",xu[r]-xu[l]+1);elseprintf("%d\n",max(wei[l]-l+1,RMQ(wei[l]+1,r)));}}return 0;
}
这篇关于POJ 3368 RMQ--ST的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
