UVA Problem F: Frequent values
University of Ulm Local Contest
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!
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int maxn=100100; 9 int cnt=0; 10 struct node 11 { 12 int L,R,nb,v; 13 }N[maxn]; 14 15 int dp[maxn+10][20]; 16 int a[maxn+10],kt[maxn+10],n,m; 17 18 int RMQ_init() 19 { 20 for(int i=1;i<=cnt;i++) dp[i][0]=N[i].nb; 21 for(int j=1;(1<<j)<=cnt;j++) 22 { 23 for(int i=1;i+(1<<j)-1<=cnt;i++) 24 { 25 dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 26 } 27 } 28 } 29 30 int RMQ(int L,int R) 31 { 32 int k=0; 33 while(R-L+1>=(1<<k)) k++; k--; 34 return max(dp[L][k],dp[R-(1<<k)+1][k]); 35 } 36 37 38 39 int main() 40 { 41 while(scanf("%d",&n)&&n) 42 { 43 scanf("%d",&m); 44 ///yu chu li 45 memset(N,0,sizeof(N)); 46 scanf("%d",a+1); 47 cnt=0;N[cnt].v=a[1];N[cnt].L=1;N[cnt].nb=1; 48 for(int i=2;i<=n;i++) 49 { 50 scanf("%d",a+i); 51 if(a[i]==N[cnt].v) 52 { 53 N[cnt].nb++; 54 } 55 else 56 { 57 cnt++; 58 N[cnt-1].R=i-1; 59 N[cnt].L=i;N[cnt].v=a[i];N[cnt].nb=1; 60 } 61 if(i==n) N[cnt].R=n; 62 } 63 int pos=1; 64 kt[0]=-1; 65 for(int i=0;i<=cnt;i++) 66 { 67 int temp=N[i].nb; 68 while(temp--) 69 { 70 kt[pos]=i; 71 pos++; 72 } 73 } 74 RMQ_init(); 75 while(m--) 76 { 77 int a,b,na=-1,nb=-1; 78 scanf("%d%d",&a,&b); 79 na=kt[a],nb=kt[b]; 80 if(na==nb) 81 { 82 printf("%d ",b-a+1); 83 } 84 else if(na+1==nb) 85 { 86 printf("%d ",max(N[na].R-a+1,b-N[nb].L+1)); 87 } 88 else 89 { 90 int ans1=N[na].R-a+1,ans2=b-N[nb].L+1,ans3=0; 91 int L=na+1,R=nb-1; 92 ans3=RMQ(L,R); 93 printf("%d ",max(ans1,max(ans2,ans3))); 94 } 95 } 96 } 97 return 0; 98 }