Peace on you code forces Community
Currently, I'm trying to solve this problem.
I think the solution is a standard Mo algorithm,
I think the minimum cost will be to give the highest frequency value = 1 and the next highest frequency value = 2 and so on,
but How to compute the answer for each query,
I have tried to store each frequency in a set and for each frequency store the number it repeated but it gives TLE in test 15, I also see some code in git hub but I didn't understand what he is doing.
can you help, thank you.
I had to look at solution but I now understand it and thought it was interesting. The idea is quite simple but i've never seen it before.
Hopefully it is obvious how to maintain your answer if you have a range and shift the left or right position by 1 (if not that's you're new goal to solve). Now what you do is you sort the queries by putting the left bounds into blocks of sqrt(n) size, and if they're the same sort by right bound directly. Now you can just iterate through the sorted queries and shift the previous left and right bound as necessary by 1 until it becomes the bound of the current query.
This works because the right bound is only increasing for left bounds within a block, so if there are k queries with a left bound within a block, the time complexity for that block is O(ksqrt(N) + n), because the left will have to move at most sqrt(n) positions for each query, and the right will move only forward at most the length of the array. Now if we number the blocks, 1, 2, ..., sqrt(n), and denote the amount in the blocks by ki, where i is the blocks number, the total complexity is O((k1 + k2 + ...) * sqrt(n) + n * sqrt(n)) = O(sqrt(n) * (n + q)) because the sum of k's is q and for each query the left bound will have to move at most sqrt(n) positions, and the right bound will have to move at most n positions for each block and there are sqrt(n) blocks.
Thank you, you are describing sqrt decomposition, I know that but how to maintain my answer
I don't know, for example, if the current range contains {1, 1, 1} I know the answer will be 3,
and if the range contains 2 different numbers the answer will be the highest frequency + 2 * second frequency.
and so on but how I keep track of that in O(1)(after moving left and right pointers), I'm able to do that in log time which is slow, I really would like to understand the technic used to compute in O(1), Thank you.
Oh I finally understand the difference between plain sqrt decomposition and mo's algorithm thonk. I thought they were both the same thing where you precomputed sqrt block sizes rip.
Anyway to answer your question, renumber the elements so they are 0, 1, 2, etc., so you can use them as array indices. Now you need to continuously hold count of the amount of each type of element in your range, and hold the count of how many element types have >= 1, 2, etc. amount in that range. Call the first array amt[] and second array cnt[]. Now you're implicitly hold the value given to each type using the cnt[] array.
When you move the right index left 1, if the element your on is type x you want to subtract cnt[amt[x]] from your current sum, subtract 1 from cnt[amt[x]], and subtract 1 from amt[x]. This is because if your getting rid of the element you can think it as the most expensive element right now with amount >= amt[x], and you are getting rid of one of the elements. Similarly if you move the right index right 1 and the new element is type x, you add 1 to amt[x], add 1 to cnt[amt[x]], then add cnt[amt[x]] to your current sum. This is because x can be thought of as the most expensive element with amount >= amt[x], so when you add one to amt[x] you need to add its expense to the sum. The moves are equivalent for the left bound. You can see this is always correct because cnt[] will have larger values with types with smaller amounts, and it will be a distinct cost because it is the dependent on the rank of the amount of the type.
thank you :D