How to efficiently get frequency of subranges and update its values altogether?

Question

I'm trying to solve the following problem:

There are N notes in an array (2<=N<=10⁵) labeled 0..N-1, all of them initially set to 1. Then there follows Q operations to perform in the array (1<=Q<=10⁵).

The task for each operation is:

• Find the most frequent value between the inclusive range [A,B].
• Add that value to all elements in the same range. The new values must be in range [0..8], then we take it modulo 9.

At the end, output all array values.

---

This is the first problem of "Maratona de Programação da SBC – ACM ICPC – 2017" here in Brazil, and I'm trying to solve it in the URI Online Judge site. Time Limit: 1 second.

---

First I tried SQRT Decomposition because it looked good, but it's not. This week I came up with a few nice ideas to solve it using Segment Tree. I was so sure my code was perfect... but it wans't. Time limit exceeded again.

I don't have Advanced Data Structures classes, I learn those things by myself. So I'm probably lacking some fancy tree structure that would solve this problem really faster. Please, give me some resource to learn such a structure.

---

Here is an Ideone link to my code. Let me describe the few nice ideas using Segment tree that I mentioned above:

• Storing the difference (delta) instead of values. With that I was able to update the ranges without going to the leaf nodes. And to find value of some node, ex: leaf node [0,0] for N=8, I can traverse from root to that node and sum up delta values [0,7].delta + [0,3].delta + [0,1].delta + [0,0].delta.
• Store in each node the count of every value [0..8] in its descendants and itself. Because each node represents a subrange, then the frequencies can be precalculated.
• Instead of recalculating the subrange array of frequencies, I can rotate it. Ex: If the most frequent note is 3, the previous quantity of values 2 is now the quantity of values 5, and so on... so rotating makes sense instead of calculating the quantities of descendant nodes again.
• This is the most brilliant, I think. Instead of rotating, use the value (calculated using delta since root path) to find which index of the frequency subrange array should be treated as the first index 0.

I spent more than twenty hours over this week since the first version of the segment tree approach. It was not easy to think all the ideas I listed above. I know I'm not the best at it. But I think you can feel how frustrated I am, after getting Time Limit Exceeded in all of my attempts.

I also think I evolved since the Square Root Decomposition approach. The problem is that I am out of ideas to improve it further. If I didn't see that 156 people have already solved it. I would think it is impossible.

Please, share a bit of your knowledge with me. Thanks in advance.

Answer 1

Almost one year later... I tried to solve it today without looking my previous code and I got ACC'ed now. (ideone link)

Reading my question now, I've implemented what I called delta and rotate in a simpler way. I will try to illustrate.

This is how the segment tree for N = 5 looks like after build():

My node struct has:

int freq[9], i, lazy;

The i variable is the position circled in red in the picture, it will hold which position of the freq array contains the frequency for note 0 (which initially is zero). The lazy flag stores pending sums for children (both left and right), blue in the picture.

Now suppose first query for [1, 2]. The query() function will find nodes [1, 1] and [2, 2] and the resulting int fquery[9] array will have values [0,2,0,0,0,0,0,0,0]. The greatest() value then is 1. Ok, this is a simple search.

Now the function chord() will update those ranges by setting lazy += 1 and i -= 1:

Note that since those are leaf nodes, the lazy property does nothing. Also note that since i was decreased, there is no need to update freq[] array. This two things were done in the pre-order traversal of the recursive chord() function.

Now we update the freq[] array of the parents using the post-order traversal of the recursive chord() function by calling update(), this update function is just a merge of left and right child nodes:

These separation of pre-order and post-order traversal of the recursive call was the main point that I didn't understand last year. I was trying to update the parents out of the recursion track, and it caused me TLE.

Now suppose second query for [0, 4]. The query() function will find node [0, 4] and the resulting int fquery[9] array will have values [0,3,2,0,0,0,0,0,0]. The greatest() value then is 1.

Now the function chord() will set lazy += 1 and i -= 1:

Since we found the desired range in the root, this time we don't have post-order traversal.

Now suppose third query for [0, 2]. The query() function will find node [0, 2]. But, we can only reach a node if there is no pending sums. So, we need to resolve the lazy = 1 flag of node [0, 4]. This is what propagate() function does:

Note: the i value of node [0, 2] is 8.

And the resulting int fquery[9] array will have values [0,0,1,2,0,0,0,0,0]. The greatest() value then is 3.

Now the function chord() will set lazy += 3 and i -= 3:

As previously, we update the freq[] array of the parents using the post-order update():

To get the output after all queries, you just need to propagate() every node, doing so the leaf nodes will have the final values. You can check the show() function.

The output for this example will be: 5 6 6 2 2. (The first test case in the URI Online Judge).

---

Conclusion: The solution to the problem is a standard segment tree with lazy propagation with each node containing an int freq[9] array and an additional index starter holder.