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
UPD: I thought K is fixed.
TselmegKh Actually K is changing in each query. so if i understood your approach correctly, it would not work.
You should have a variable that keeps count on how many elements have a frequency greater or equal to k. This variable you only have to update it whenever a number gets to frequency k or k — 1.
suppose currently in range (1,10) 5 element have frequency greater than k. so ans is 5 now. now in next query range is same i.e. (1,10) but new k is k-2. Then in mo algorithm no add or remove function will be called and ans will remain same. which can be wrong
you can use BIT (binary indexed tree)as an additional data structure along with map, this BIT maintains the count of elements with particular frequency , now answer for a query is simply query(n)-query(K-1);
Use a BST where you can get index of a value. Use this as your frequency "array". This way it is always sorted so you can calculate how many values are before/after k.
It is also possible to use a segment tree instead. Put a 1 on position i if freq[x]=i for some x. if there are two different values with same frequency, put a 2 there etc. You can now query sum in l..r to see how many different values have frequencies between l and r.
Thanks a lot. I got your BST approach.
one question in your second approch. We need to sort the queries by increasing order of their right end. And query the sum between (K,'maximum frquency till now') in segment tree of your array.Am i Right?
Both approaches still use Mo's algo, so you sort the queries in Mo's algo order.
But this will be complexity O(n * sqrt(n) * log(n)) so maybe too slow.
Ohhk. Got it, Thanks a lot. And the question that I am trying is having 5 sec time limit so I think it should work.
you can use a fenwick tree for finding the no of elements with frequency>=k
ISuckAtLife can you please give me the problem link? I want to solve it. Though it can be hard as it's a post from 10 months ago.
Use block technique to keep total complexity in O(n*sqrt(n)). In detail, maintain the frequency arry $$$Bi$$$ of each element $$$Ai$$$ and calculate the sum for each block. In this way you can move endpoint in O(1) complexity and answer each query in O(sqrt(n)).