Help with MO algorithm Question

Revision en1, by ISuckAtLife, 2019-07-09 18:30:00

We are given A array with N elements and Q queries are done on it. In each query, a range (L,R) and a no. K is given and we have to find no of element with frequency >=K in that range.

constraints A[i]<=1e6

N<=1e5

Q<=1e5

I am trying to do it using MO algorithm. Kepping an array to store frequency of each element. But how do i find elements with frequency >= k without transversing (otherwise complexity will be much higher)

Thanks in advance

Tags mo algorithm, #range query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ISuckAtLife 2019-07-09 18:30:00 501 Initial revision (published)