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!
You can do this with Mo's algorithm, you can read more about it here. Note how the very problem they used there to explain the algorithm is similar to this :)
In this particular case the complexity would be O(nsqrtlog^2n). Kinda sad imo :(
Oops. I didn't notice k will vary for each query here. Sorry about that.
You can still do it in O(n*sqrt(n)*log(n)) though. You can maintain a segment tree or set on the frequency of elements.
Suppose the current frequency of the element you want to insert now is f. So, you will increase value of (f+1)-th node in segment tree by 1, and decrease value of f-th node by 1.
Same way, you do +1 to (f-1)-th node and -1 to f-th node while removing an element.
While querying, sum of range k to end is the answer.
But this takes around 5*10^8 operations which is still pretty costly :/
Edit: pranet described the n*sqrt solution, no need of any log factor at all.
Ah, my bad. I initially though about maintaining a segment tree (on numbers themselves, not frequencies) with treaps inside. But your approach is much better :)
I thinks it's possible to do this in O(N sqrt(N)). Through Mo's you need to maintain two arrays: app[] and kfreq[]; the former indicates for every element i how many appearsances of the said element i are there in the current segment; on the other hand, kfreq[i] will hold how many elements j are there such that app[j] > = i. Both updates on the arrays can be done in O(1). Then, for a query (L, R, K) you just need to consult kfreq[K].
O(n * sqrt(n)) solution
Run MO's. Maintain two arrays, arr[] and cnt[]
arr[i] = number of elements with frequency atleast i
cnt[i] = frequency of element i
When you add an element x, ++cnt[x], ++arr[cnt[x]];
When you delete an element, --arr[cnt[x]], --cnt[x];
Answer for a query = arr[k]
Should be arr[k] prob?
Yet I don't see how you're gonna update everything in arr in constant time. It's >=, not just =.
After you add +1 to cnt[x], it means that there is one more number now equal to or larger than arr[cnt[x]], so you just ++arr[cnt[x]]. When cnt[x] decreases, there no longer will be that number, so he is doing --arr[cnt[x]] before decreasing.
Here's an example.
Suppose whole array is 1 1 2 and first range contains 1 1.
When you get first 1, cnt[1] becomes 1, arr[cnt[1]] i;e arr[1] becomes 1. When you get second 1, cnt[1] becomes 2. arr[2] becomes 1.
So if you query k = 1 now, you will find answer as arr[1], if k = 2, answer will be arr[2].
If the next range is 1 2, you have to remove the first 1. So you have to do --cnt[1]. But then, arr[2] no longer will be 1, it will need to decrease too as cnt[1] will no longer be 2. So before doing --cnt[1], you first decrease arr[cnt[1]] i;e arr[2], it will become 0, then you do --cnt[1], it becomes 1.
So now if you query k = 2, you will see arr[2] is 0 i;e no number has frequency >= 2.
Tricky but you're right, thnx :)
UPD: I misreaded. Sorry for inconvenience.
Sorry for my poor English.
Actually we don't need to use BIT.
Let p[i] be the number of x such that a[x] >= i and we can maintain it in O(1) time.
For instance, if we need to add +1 to a[i] , simply making p[a[i]+1]++ is enough.
For a query the answer will just be p[k] .
The total time complexity is O(qsqrt(n)), without the log .
(Sorry for my bad English >_< )
Here I have a Python ONE LINER solution for the same. Assuming l and r are q[0] and q[1]:
return [sum(1 for y in dict(Counter(arr[x[0]-1:x[1]])).values() if y>=k) for x in query]
No you don't.
The only reason this question was asked (4 years ago!) is because it's not clear how to do it with good time complexity. Naive solutions, however short, are not relevant to this discussion.
so what dude? I am just sharing my solution. That's my personal choice. Why do you have to break your head for that? Just calm down! Ok bro? The post was not about finding an optimal solution, it was about him not being able to solve the problem. I am sorry if I am being rude here. But I am getting so much down votes from the community for sharing my solution with this world. Quite discouraging!!!
Considering that OP mentions square-root decomposition in the post, they definitely had time complexity in mind.
Also, the downvotes are in part due to this post being 4 years old.
OP also mentioned in the previous line that "I've though on this for a while, and can't get any idea how to solve this", which means he didn't know to solve it but just had an option in his mind. But I didn't do anything wrong by sharing my one liner code. I thought pythonic people like me searching for an approach would actually be benefited by my code. But instead I got so much downvotes here. Felt really bad for stepping out to help. :(
The limits of the inputs are given, which is a clear indication that execution speed was the most important aspect. The solution you provided obviously does not meet such requirement. I'm not even mentioning how short, Pythonic codes in some cases can do more harm than good.
This leads to another problem: you failed to provide a good solution, while the post is 4 years old. You can literally see this warning right above the "Post" button:
I believe if you do the same thing on other sites/forums, you will most likely receive the same responses.