### Блог пользователя UmCaraLegal

Автор UmCaraLegal, история, 9 месяцев назад, ,

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

Thank you :) and sorry for my bad english

•
• +11
•

 » 9 месяцев назад, # |   0 Auto comment: topic has been updated by UmCaraLegal (previous revision, new revision, compare).
 » 9 месяцев назад, # |   0 Is there an online way faster than N log^2 N? I couldn't find one.
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 farmersrice Could you share it? :D
•  » » » 9 месяцев назад, # ^ |   +3 My bad, I was thinking of finding majority, not mode.
 » 9 месяцев назад, # |   +89 It's strongly believed that it is impossible to do so it in even offline. There is a reduction from multiplication of two binary matrices of size to this problem, and the best known matrix multiplication algorithm at the moment is O(n2.37...). This yields a lower bound for this problem, and if you solve it in quasi-linear time it would be a breakthrough whose significance is comparable with solving P vs NP.By the way, the name for the problem is "finding mode on a subsegment".P.S. Downvoted for "sorry for bad English" part. C'mon, folks, stop adding it to each and every blogpost!
 » 9 месяцев назад, # | ← Rev. 2 →   +1 It can be solved online in per query :)
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 GreenGrape Could you explain this solution ? :D
•  » » » 9 месяцев назад, # ^ |   0 Let's split the array into blocks of size A. For each possible range of (some block start, some block end) compute three arrays: frequency of each number, the amount of numbers that give such frequency and one more (I will talk about it later). This will take time and memory.Now to obtain all existing frequences for an [L..R] segment you have to find the largest range that you've already computed the answer for and stretch it to the left and to the right. This will take O(A) for both ends.But this is not enough because to answer the "most frequent" query you have to iterate over the entire frequences array which takes O(N) time. Try to guess what should be done to reduce the complexity to with some additional array which I mentioned in the beginning :)Talking about A, the optimal choise would be .
•  » » 9 месяцев назад, # ^ |   +5 It can be solved online in time per query and linear memory, though it is rather complicated.
 » 9 месяцев назад, # |   0