I recently attempted this problem https://www.codechef.com/COOK77/problems/CHEFNUMK
using MO's algorithm (offline sqrt decomp) but got TLE. Almost everyone used the same method to reach AC. Changing values of blocks affects the complexity is known, and i tried a few values. Comparing the following code
https://www.codechef.com/viewsolution/12297863
with my code
https://www.codechef.com/viewsolution/12299180
doesn't show much difference, help ?
You don't have to keep a BIT or any type of structure for answering. Just keep an array nr[i] = number of values in [l,r] at the actual step which have frequencies >= i. It's pretty easy to see how this array changes when you move with left or right.
To give you an example, if you move right to right + 1 and a[right + 1] = x then nr[freq[x] + 1]++ and freq[x]++. freq[x] = frequency of value x.
Having this array is pretty easy to answer the question. Is number of different values in [l,r]-nr[k + 1].
True, the logn factor will affect the complexity and i should have given some more thought to it. Though what i wanted to know is many submissions passed with
(N+Q)sqrtN*logN complexity in under 0.5 secs! There should be some other constants in play !
True, I used MO + segment tree but it didn't pass TL. Though fenwick is faster than segment tree but still it would be great if some one can show an AC solution with segment tree.
Good day to you,
Well here is a "Segment Tree + MO" solution, but not sure if it is what you wanted (it is kinda slower than FW so it has "a few" optimizations {the code — not the ST})
Have nice day ^_^
Thanks :) Good day to you too ;p