As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

Most frequent value in a range

Revision en1, by UmCaraLegal, 2017-09-14 02:46:21

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]])

Thank you :) and sorry for my bad english

Tags segment tree, mos_algorithm, sqrt-decomposition, persistent segment trees, data structure

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English UmCaraLegal 2017-09-14 02:49:44 42 Tiny change: 'A[i]])\n\n\n**Th' -> 'A[i]])\n\n**Code :** http://codepad.org/0D7V5uha\n\n\n**Th'
en1 English UmCaraLegal 2017-09-14 02:46:21 1150 Initial revision (published)