### tom's blog

By tom, history, 4 years ago, Hello everyone!

I've been thinking about solution to the following problem for few days and didn't come up with any reasonable idea. Could you help me out?

You're given array of n elements and q queries. Every query is one of two type:

1) Reverse interval [l, r], e.g. for array 1 2 3 4 5 6 and query [2, 5] we end up with 1 5 4 3 2 6.

2) Ask for sum on interval [l, r].

Thanks and have a nice Sunday.  Comments (9)
 » This is quite simple to do using treaps and lazy propagation on them. You can find resources by googling.
•  » » where can i find tutorial for treap in english?
•  » » »
•  » » » » That was really helpful!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   https://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-2https://e-maxx-eng.appspot.com/data_structures/treap.htmlBurunduk1 code for a treap with reverse.I honestly don't know how good are these tutorials since I learned about treaps at the university. As it was mentioned, the problem can be solved using SQRT decomposition
•  » » » » Thank you :)
 » can you post the link to the question?
 » If you want a solution not using treaps then read burunduk1's lecture note. (The Split and Rebuild variant)
 » There is no need of boggling with treaps .Here is a sollution.Time comlexity is still log(N) for each query. First, let's solve the simple problem. Given an array and in each query, you are given L and R. You have to find the maximum sub-array sum between L and R(both inclusive). This question can be solved using segment trees Now in this question for every query, the segment from L to R is reversed and we have to find the maximum sub-array sum after reversing the segment. Now find the maximum sub-array sum, maximum prefix, maximum suffix and the total sum of the segment from L to R. If the maximum sub-array lies completely inside the range from L to R then the answer is the answer of the node from L to R . (refer to my solution). If the maximum sub-array doesn't overlap with the segment [L, R] then we need to take the maximum sub-array sum from the segment [1, L-1] and [R+1, N] which we need to precompute. If the sub-array overlap with the segment [L, R] then there are three possibilities. the answer can be max_end_here[L-1]+node.suffix (or) max_start_here[R+1]+nide.prefix (or) node.sum+max(0LL,max_start_here[R+1])+max(0LL,max_end_here[L-1]) now the answer is the maximum of all the above defined cases. Note: we need to take care of corner cases like L=1 and R=N. You can refer to my solution. https://ideone.com/mGwIch