I am trying to solve the last question in the EDU lesson on Segment Trees part 1 on Codeforces.
Here is the question.
My approach: Store a map at each node of the segment tree. Instead of using the maps of the two children to get the new map, we can be clever and use the invertibility of the operation. Thus the set operation can be done in O(log^2(n)).
Now the range query is tricky, as I need to modify the tree. In the worst case, I would have to modify the map in every node, which seems too much. I know I can do optimizations like not storing 0 as a key and only changing the map for keys less than p, but still feels like it won’t pass. Is this a lazy-propagation question ( as I can answer queries quickly if I don’t update the segment tree, but the answer for the next query will be wrong)?
Or I am overthinking it and there is a very easy solution? This problem is in the Basic segment tree lectures and shouldn’t use advanced concepts.