[UVA] 11235 - Frequent values
University of Ulm Local Contest
Problem F: Frequent values
You are given a sequence of n integersa1 , a2 , ... , anin non-decreasing order. In addition to that, you are given severalqueriesconsisting of indices i and j (1≤ i ≤ j ≤ n). For each query, determine themostfrequent 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 nand q (1 ≤ n, q ≤ 100000).The next line contains n integersa1 , ... , 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 thequery.
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 withinthe given range.
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 100
Sample Output
143
作法 : http://bleed1979-psdr.blogspot.com/2011/10/11235-frequent-values.html
主要想法還是 RMQ, 在連續的部分猜成中間那段保證連續, 其他用扣的
#include<stdio.h>
#include<string.h>
int SparseTable[100000][20];
int BinaryExpFloor(int n) {
return (int)floor(log10(n)/log10(2));
}
int Max(int x, int y) {
return x > y ? x : y;
}
int Leftmost[100000], Rightmost[100000];
int Build(int *A, int n) {
int i, j, k, t;
int tmp = 0, before = A[0];
for(i = 0; i < n; i++) {
if(A[i] == before) tmp ++;
else {
j = i-1;
while(j >= 0 && A[i-1] == A[j]) SparseTable[j--][0] = tmp;
tmp = 1;
}
before = A[i];
}
j = i-1;
while(j >= 0 && A[i-1] == A[j]) SparseTable[j--][0] = tmp;
Leftmost[0] = 0, Rightmost[n-1] = n-1;
for(i = 1; i < n; i++)
if(A[i] == A[i-1]) Leftmost[i] = Leftmost[i-1];
else Leftmost[i] = i;
for(i = n-2; i >= 0; i--)
if(A[i] == A[i+1]) Rightmost[i] = Rightmost[i+1];
else Rightmost[i] = i;
for(k = 1, t = 2; t < n; k++, t <<= 1)
for(i = 0; i+t <= n; i++)
SparseTable[i][k] = Max(SparseTable[i][k-1], SparseTable[i+(t>>1)][k-1]);
}
int query(int i, int j, int *A) {
int ni, nj, k, Ans = 0;
ni = Rightmost[i]+1, nj = Leftmost[j]-1;
if(ni <= nj) {
k = BinaryExpFloor(nj-ni+1);
Ans = Max(SparseTable[ni][k], SparseTable[nj-(1<<k)+1][k]);
Ans = Max(Max(Ans, (ni-1)-i+1), j-(nj+1)+1);
} else {
if(A[i] != A[j])
Ans = Max(ni-i, j-nj);
else
Ans = j-i+1;
}
return Ans;
}
int main() {
int n, q, A[100000], i, x, y;
while(scanf("%d", &n) == 1 && n) {
scanf("%d", &q);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
Build(A, n);
while(q--) {
scanf("%d %d", &x, &y);
printf("%d\n", query(x-1, y-1, A));
}
}
return 0;
}