Finding the number of elements that have frequency <= k, in a given range

Правка en1, от color_me_red, 2017-07-07 21:49:43

With an array of size  ≤ 105, and with every a[i] in the range 1 ≤ a[i] ≤ 105, there are  ≤ 105 queries.

Each query is of the form [l, r, k], and the output should the number of elements that appear  ≥ k times in a[l]..a[j]. I've though on this for a while, and can't get any idea how to solve this. I've seen a similar problem before but can't find the statement anywhere.

I'm thinking squareroot decomposition could work, but have no clue to proceed. Thanks for any help!

Теги range query

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский color_me_red 2017-07-07 21:54:30 2
en1 Английский color_me_red 2017-07-07 21:49:43 577 Initial revision (published)