Algorithm
Problem link- https://www.spoj.com/problems/FREQUENT/
FREQUENT - 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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
const int N = 1e5+5;
const int M = 1e5+5;
const int SQN = sqrt(N) + 1;
struct query{
int l, r;
int idx;
int block;
query(){}
query(int _l, int _r, int _id){
l = _l;
r = _r;
block = _l/SQN;
idx = _id;
}
bool operator < (const query &b) const{
if(block != b.block)
return block < b.block;
return r < b.r;
}
};
query Q[M];
int ans[M];
int n, q;
int arr[N];
int freq[N], counter[N];
int main(){
while(1){
scanf("%d", &n);
if(n == 0)
break;
scanf("%d", &q);
for(int i = 1;i <= n; i++)
scanf("%d", arr+i);
for(int i = 1;i <= q; i++){
int l, r;
scanf("%d%d", &l, &r);
// l++;r++;
Q[i] = query(l, r, i);
}
sort(Q+1, Q+1+q);
int curl = 1, curr = 0;
int t_ans = 0;
for(int i = 1;i <= q; i++){
int l = Q[i].l;
int r = Q[i].r;
int idx = Q[i].idx;
while(curr < r){
++curr;
int val = arr[curr];
int c = freq[val];
counter[c]--;
freq[val]++;
counter[freq[val]]++;
t_ans = max(t_ans, freq[val]>;
}
while(curl > l){
--curl;
int val = arr[curl];
int c = freq[val];
counter[c]--;
freq[val]++;
counter[freq[val]]++;
t_ans = max(t_ans, freq[val]);
}
while(curr > r){
int val = arr[curr];
int c = freq[val];
counter[c]--;
freq[val]--;
counter[freq[val]]++;
while(counter[t_ans] == 0) t_ans--;
--curr;
}
while(curl < l){
int val = arr[curl];
counter[freq[val]]--;
freq[val]--;
counter[freq[val]]++;
while(counter[t_ans] == 0) t_ans--;
++curl;
}
ans[idx] = t_ans;
}
for(int i = 1;i <= q; i++){
printf("%d\n", ans[i]);
}
}
return 0;
}Input
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Output
4
3
Demonstration
SPOJ Solution-Frequent values-Solution in C, C++, Java, Python