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!
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; const int maxn=;
int cnt=;
struct node
{
int L,R,nb,v;
}N[maxn]; int dp[maxn+][];
int a[maxn+],kt[maxn+],n,m; int RMQ_init()
{
for(int i=;i<=cnt;i++) dp[i][]=N[i].nb;
for(int j=;(<<j)<=cnt;j++)
{
for(int i=;i+(<<j)-<=cnt;i++)
{
dp[i][j]=max(dp[i][j-],dp[i+(<<(j-))][j-]);
}
}
} int RMQ(int L,int R)
{
int k=;
while(R-L+>=(<<k)) k++; k--;
return max(dp[L][k],dp[R-(<<k)+][k]);
} int main()
{
while(scanf("%d",&n)&&n)
{
scanf("%d",&m);
///yu chu li
memset(N,,sizeof(N));
scanf("%d",a+);
cnt=;N[cnt].v=a[];N[cnt].L=;N[cnt].nb=;
for(int i=;i<=n;i++)
{
scanf("%d",a+i);
if(a[i]==N[cnt].v)
{
N[cnt].nb++;
}
else
{
cnt++;
N[cnt-].R=i-;
N[cnt].L=i;N[cnt].v=a[i];N[cnt].nb=;
}
if(i==n) N[cnt].R=n;
}
int pos=;
kt[]=-;
for(int i=;i<=cnt;i++)
{
int temp=N[i].nb;
while(temp--)
{
kt[pos]=i;
pos++;
}
}
RMQ_init();
while(m--)
{
int a,b,na=-,nb=-;
scanf("%d%d",&a,&b);
na=kt[a],nb=kt[b];
if(na==nb)
{
printf("%d\n",b-a+);
}
else if(na+==nb)
{
printf("%d\n",max(N[na].R-a+,b-N[nb].L+));
}
else
{
int ans1=N[na].R-a+,ans2=b-N[nb].L+,ans3=;
int L=na+,R=nb-;
ans3=RMQ(L,R);
printf("%d\n",max(ans1,max(ans2,ans3)));
}
}
}
return ;
}