Finding subarray maximum is a very common problem. With value updates in specific positions, it can easily be solved with a segment tree. If you haven’t solved such problems yet, you may want to try it before as you’ll need a similar approach anyway.
Let’s divide the solution into some sub problems,
i. To be able to find range max query for a given range. ii. To be able to handle change signs of all values in a given range. iii. To be able to cut a sub-array of size X and merge anywhere in an array.
Let’s assume we’re storing prefix_max, prefix_min, suffix_max, suffix_min, ans_min, ans_max.
For (ii), you can easily use a lazy approach for segment tree solutions where you can just swap all the mins with maxes when you reach a node_completely_within_ranges.
For (iii), segment tree won’t work in any normal approach and honestly, I don’t think it’s possible to solve using segment tree. Here we’ll need a rope-like data structure that can cut any range and merge it anywhere under O(logN) time complexity. Here a balanced binary tree or a treap can potentially help you do the cutting and merging in O(logN) complexity while following your given ruleset. But yes, you’ll quite possibly need to implement the lazy approach in these data structures as well. I’ll leave (i) to you and it shouldn’t be a problem if you’ve come this far. However, as a hint, you can find the query answers easily in O(logN) as well using such data structures. So, the overall complexity of the solution will be O(QlogN).
