Algorithm

Problem link- https://www.spoj.com/problems/FREQ2/

FREQ2 - Most Frequent Value

#ad-hoc-1 #sqrt-decomp

 

You are given a sequence of n integers a0, a1 ... an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai ... aj.

Input

First line contains two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a0 ... an-1 (0 ≤ ai ≤ 100000, for each i ∈ {0 ... n-1}) separated by spaces. The following q lines contain one query each, consisting of two integers i and j (0 ≤ i ≤ j ≤ n-1), which indicates the boundary indices for the query.

Output

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Example

Input:
5 3
1 2 1 3 3
0 2
1 2
0 4

Output:
2
1
2

 

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(){
	scanf("%d%d", &n, &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;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5 3
1 2 1 3 3
0 2
1 2
0 4

Output

x
–
+
cmd
2
1
2
Advertisements

Demonstration

SPOJ Solution-Most Frequent Value-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python