Hi everyone !↵
↵
We have a static array of size N and Q queries. Each Query given us two integers i and j.↵
↵
For each query we need to answer what is the maximum frequency of the values of this range.↵
↵
For example:↵
↵
A = {3, 4, 3, 4, 4, 1 } ↵
↵
Query(0, 2) = 2 (The value 3 repeat 2 times)↵
↵
Query(0, 5) = 3 (The value 4 repeat 3 times)↵
↵
The problem can be found here : http://www.spoj.com/problems/FREQ2/↵
↵
**1 <= N, Q <= 100000, 0 <= A[i] <= 100000**↵
↵
**OBS:** _I would like to know if this problem is possible to solve "online" and the total complexity O(N*log(N))_↵
__↵
_If you have any idea comment bellow, please :D._↵
↵
**Solution using Mo's algorithm (Offline Queries and O(N*sqrt(N)) :**↵
↵
You need to save the value's frequency in a array.↵
↵
Freq[i] will determine how many times the value "i" has been appears in our current array↵
↵
Every times you will need to remove a element, decrease Freq[A[i]] by one and check if your answer should be changed↵
↵
And for Add a element, increase Freq[A[i]] by one and do: answer = max(answer, freq[A[i]])↵
↵
**Code :** http://codepad.org/0D7V5uha↵
↵
↵
**Thank you :) and sorry for my bad english**↵
↵
We have a static array of size N and Q queries. Each Query given us two integers i and j.↵
↵
For each query we need to answer what is the maximum frequency of the values of this range.↵
↵
For example:↵
↵
A = {3, 4, 3, 4, 4, 1 } ↵
↵
Query(0, 2) = 2 (The value 3 repeat 2 times)↵
↵
Query(0, 5) = 3 (The value 4 repeat 3 times)↵
↵
The problem can be found here : http://www.spoj.com/problems/FREQ2/↵
↵
**1 <= N, Q <= 100000, 0 <= A[i] <= 100000**↵
↵
**OBS:** _I would like to know if this problem is possible to solve "online" and the total complexity O(N*log(N))_↵
__↵
_If you have any idea comment bellow, please :D._↵
↵
**Solution using Mo's algorithm (Offline Queries and O(N*sqrt(N)) :**↵
↵
You need to save the value's frequency in a array.↵
↵
Freq[i] will determine how many times the value "i" has been appears in our current array↵
↵
Every times you will need to remove a element, decrease Freq[A[i]] by one and check if your answer should be changed↵
↵
And for Add a element, increase Freq[A[i]] by one and do: answer = max(answer, freq[A[i]])↵
↵
**Code :** http://codepad.org/0D7V5uha↵
↵
↵
**Thank you :) and sorry for my bad english**↵