首页 > 代码库 > UVA 11235 Frequent values(RMQ)
UVA 11235 Frequent values(RMQ)
Frequent values
TimeLimit:3000Ms
You are given a sequence 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 Specification
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 Specification
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
0
Sample Output
1
4
3
题意:给出一个非降序排列的数组A1,A2,A3,……,An,对于一系列询问(i,j),输出Ai,A(i+1),……,Aj中出现次数最多的值出现的次数。
分析:因为整个数组是非降序的,所有相等元素会聚集在一起,这样就可以把这个数组进行游标编码,比如-1,1,1,2,2,2,4就可以编码成(-1,1),(1,2),(2,3),(4,1),其中(a,b)表示有b个连续的a。用value[i]和count[i]分别表示第i段的数值和出现次数,num[p]、left[p]、right[p]分别表示位置p所在段的编号和左右端点位置,则每次查询时的结果为以下三部分的最大值:从L到L所在段的结束处的元素个数(即right[L]-L+1)、从R所在段的开始处到R处的元素个数(即R-left[R]+1)、中间第num[L]+1段到第num[R]-1段的count的最大值。这样问题就几乎转化为了RMQ问题。
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<iostream> using namespace std; const int N = 1e5 + 10; int n, tot, Q; int dp[N][20]; int num[N], cnt[N], Left[N], Right[N]; void RMQ_Init() { memset(dp, 0, sizeof(dp)); for(int i = 1; i <= tot; i++) dp[i][0] = cnt[i]; for(int j = 1; (1<<j) <= n; j++) for(int i = 1; i + (1<<j) - 1 <= tot; i++) dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } int RMQ(int L, int R) { if(L > R) return 0; int k = 0; while((1<<(k+1)) <= R - L + 1) k++; return max(dp[L][k], dp[R-(1<<k)+1][k]); } int main() { int v, last_v, i; while(~scanf("%d",&n)) { if(n == 0) break; scanf("%d",&Q); tot = 0; memset(Left, 0, sizeof(Left)); memset(Right, 0, sizeof(Right)); memset(cnt, 0, sizeof(cnt)); for(i = 1; i <= n; i++) { scanf("%d",&v); if(i == 1) { ++tot; last_v = v; Left[tot] = 1; } if(last_v == v) { num[i] = tot; cnt[tot]++; Right[tot]++; } else { num[i] = ++tot; cnt[tot]++; Left[tot] = Right[tot] = i; last_v = v; } } RMQ_Init(); int L, R; for(int i = 0; i < Q; i++) { scanf("%d%d",&L,&R); if(num[L] == num[R]) printf("%d\n", R - L + 1); else { int tmp1 = Right[num[L]] - L + 1; int tmp2 = R - Left[num[R]] + 1; int tmp3 = RMQ(num[L] + 1, num[R] - 1); printf("%d\n",max(tmp1, max(tmp2, tmp3))); } } } return 0; }