University of Ulm Local Contest
Problem F: Frequent values
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
A naive algorithm may not run in time!
整个数组是非降序的，所以所有相同的元素都是相邻的。可以把整个数组进行游程编码(Run Length Encoding,RLE）。比如样例中的-1 -1 1 1 1 1 3 10 10 10可以编码为(-1,2)，(1,4)，(3,1)，(10,3)，其中(a,b)表示有b个连续的a，在程序中，我用了value数组和number数组分别表示第i段的数值(a)和出现的次数(b)。
数组pos[i],Left[i],Right[i]分别保存位置i的元素所在段的下标，第一次出现这个数值的下标和最后一次出现这个数值的下标。
则每次询问的结果就是下面三个数的最大值：
1、从L到L所在段结束处的元素个数（Right[L]-L+1）
2、从R到R所在段开始处的元素个数（R-Left[R]+1）
3、中间部分（Right[L]+1到Left[R]-1）出现次数最多的元素的出现次数，即从pos[L]+1到pos[R]-1段中number的最大值
其中第三条是一个RMQ问题，可以用Tarjan的Sparse-Table算法求解（Sparse-Table算法讲解: http://www.cnblogs.com/lzj-0218/p/3539367.html）。
另外此题数据范围似乎有问题，刚开始数组大小开100050时总是RE，一怒之下全改成了200050就AC了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 6 using namespace std; 7 8 int n,t; 9 int a[200050],value[200050],number[200050],Left[200050],Right[200050],pos[200050]; 10 int rmq[200050][100]; 11 12 void RMQ_init() 13 { 14 for(int i=1;i<=n;i++) 15 rmq[i][0]=number[i]; 16 for(int j=1;(1<<j)<=n;j++) 17 for(int i=1;i+j-1<=n;i++) 18 rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]); 19 } 20 21 int RMQ(int l,int r) 22 { 23 int k=0; 24 while( (1<<(k+1)) <= r-l+1 ) 25 k++; 26 return max(rmq[l][k],rmq[r-(1<<k)+1][k]); 27 } 28 29 int Max(int a,int b,int c) 30 { 31 return a>b?(a>c?a:c):(b>c?b:c); 32 } 33 34 int main() 35 { 36 while(scanf("%d",&n)==1&&n) 37 { 38 int q; 39 40 t=1; 41 memset(number,0,sizeof(number)); 42 43 scanf("%d",&q); 44 for(int i=1;i<=n;i++) 45 { 46 scanf("%d",&a[i]); 47 if(i==1) 48 { 49 Left[0]=1; 50 value[1]=a[0]=a[1]; 51 } 52 if(a[i]!=a[i-1]) 53 { 54 Left[i]=i; 55 value[++t]=a[i]; 56 for(int j=i-1;j>=0&&a[j]==a[i-1];j--) 57 Right[j]=i-1; 58 } 59 else 60 Left[i]=Left[i-1]; 61 pos[i]=t; 62 number[t]++; 63 } 64 for(int i=n;i>=0&&a[i]==a[n];i--) 65 Right[i]=n; 66 67 RMQ_init(); 68 69 int l,r; 70 for(int i=1;i<=q;i++) 71 { 72 scanf("%d %d",&l,&r); 73 printf("%d\n",a[l]==a[r]?r-l+1:Max(Right[l]-l+1,r-Left[r]+1,pos[l]+1<=pos[r]-1?RMQ(pos[l]+1,pos[r]-1):-1) ); 74 } 75 76 } 77 78 return 0; 79 }