UVA – 11235
Frequent values
Time Limit:3000MSMemory Limit:Unknown64bit IO Format:%lld & %llu
Submit
Description
2007/2008 ACM International Collegiate Programming ContestUniversity of Ulm Local ContestProblem F: Frequent values
You are given a sequence ofnintegersa1, a2, … , anin non-decreasing order. In addition to that, you are given several queries consisting of indicesiandj(1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integersai, … , aj.
Input Specification
The input consists of several test cases. Each test case starts with a line containing two integersnandq(1 ≤ n, q ≤ 100000). The next line containsnintegersa1, … , an(-100000 ≤ ai≤ 100000, for eachi ∈ {1, …, n}) separated by spaces. You can assume that for eachi ∈ {1, …, n-1}: ai≤ ai+1. The followingqlines contain one query each, consisting of two integersiandj(1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.
The last test case is followed by a line containing a single0.
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 Input10 3-1 -1 1 1 1 1 3 10 10 102 31 105 100Sample Output143A naive algorithm may not run in time!
Source
Root :: Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim) :: Chapter 2. Data Structures and Libraries :: Data Structures With Our-Own Libraries ::Segment TreeRoot :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: Data Structures and Libraries :: Data Structures with Our-Own Libraries ::Tree-related Data StructuresRoot :: AOAPC I: Beginning Algorithm Contests — Training Guide (Rujia Liu) :: Chapter 3. Data Structures :: Maintaining Interval Data ::ExamplesRoot :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: Data Structures and Libraries :: Data Structures with Our-Own Libraries ::Tree-related Data Structures
Submit
思路：搞了我半天才搞出来，也是够啦，最后才发现是数组下标从一开始，我这代码凑合着用吧，，因为是非降序的，所以进行游程编码（RLE），再算出区间内的最大值就好了
AC代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 100005;int a[maxn];int value[maxn], coun[maxn];int num[maxn], le[maxn], ri[maxn];int d[maxn][400];int maxnum;//最大编号void RMQ_init() {for(int i = 0; i < maxnum+1; i++) d[i][0] = coun[i];for(int j = 1; (1 << j) <= maxnum+1; j++)for(int i = 0; i + (1<<j) – 1 < maxnum+1; i++)d[i][j] = max(d[i][j-1], d[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(d[l][k], d[r-(1<<k) +1][k]);}int main() {int n, q;while(scanf("%d", &n) && n!=0) {scanf("%d", &q);for(int i = 0; i < n; i++)scanf("%d", &a[i]);maxnum = 0;int cnt = 1;//当前出现次数 value[0] = a[0], coun[0] = cnt, num[0] = 0, le[0] = 0, ri[0] = 0;for(int i = 1; i < n; i++) {if(a[i] != a[i-1]) {ri[maxnum] = i – 1;cnt = 1; maxnum++;le[maxnum] = i; ri[maxnum] = i;num[i] = maxnum;value[maxnum] = a[i];coun[maxnum] = cnt;}else {cnt++;coun[maxnum] = cnt;num[i] = maxnum;ri[maxnum] = i;}}RMQ_init();for(int i = 0; i < q; i++) {int l, r;scanf("%d %d", &l, &r);l–; r–;//printf("%d %d %d\n", ri[num[l]]-l+1, r-le[num[r]]+1, RMQ(num[l]+1, num[r]-1));if(num[l] == num[r]) printf("%d\n", r – l + 1);else if(num[r] – num[l] == 1) printf("%d\n", max(ri[num[l]]-l+1, r-le[num[r]]+1));else printf("%d\n", max(max(ri[num[l]]-l+1, r-le[num[r]]+1), RMQ(num[l]+1, num[r]-1)));}}return 0;}
有希望在的地方，痛苦也成欢乐
