https://codeforces.com/contest/840/problem/D
if any one has any idea how to solve this problem maybe using mos algorithm/sqrt decomposition please share.i was trying to use fenwick tree along with it to know whether if a no. occurs >particular times(by updating its frequency in fenwick tree)but unable to come up with the idea to find the smallest number.
if anyone knows how to solve it please share your idea .
@everule1 @galencolin please help
I remember trying to squeeze that problem with some dumb O(n\sqrt{n\log{n}}) solution, if you want it, it’s here.
The basic idea is: if a query is large (length \geq C), there are at most \dfrac{N}{\frac{C}{k}} = \dfrac{Nk}{C} colors that are worth looking at, because there are too few of all other colors to ever possibly be an answer. And if a query is small (length < C), you can brute-force the answer. The first type of query takes O(k\sqrt{n}\log{n}) (because you have to binary search or something to count values) and the second takes O(\sqrt{n}) but goes ham on cache misses, so it still has a high constant. Choosing C = 600 worked best for me, so it goes to show the power of cache misses.
Also remember that it’s a Div. 1 D for a reason - the intended solution is a complicated custom segment tree.
edit: I guess you can also do Mo’s with a priority queue and look at the top k colors for a query, but it’s still a terrible complexity
3 Likes