Need help with SPOJ problem FREQ2
Difference between en1 and en2, changed 294 character(s)
I am solving problems on mo's algorithm and came across this problem [FREQ2](https://www.spoj.com/problems/FREQ2/).↵
I am using an array (inv_freq) where inv_freq[x] stores the no of distinct elements having frequency x along with a dynamically updated square root decomposed array of this to find the max frequency. I believe its complexity is O((Q+N)*sqrt(N)). My [solution](https://www.spoj.com/status/FREQ2,harsha_1_2/#) is timing out. Can someone help with a better way to find this maximum?


UPDATE: I saw this idea which uses an array where array[x] is the number of elements having frequency more than x which can be incremented and decremented with single addition of element or deletion of element to our range and binary searching over this array to find the maximum frequency.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English harsha_1_2 2020-04-23 15:40:16 294
en1 English harsha_1_2 2020-04-19 13:09:35 529 Initial revision (published)