tom's blog

By tom, history, 4 years ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

This is quite simple to do using treaps and lazy propagation on them. You can find resources by googling.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can you post the link to the question?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want a solution not using treaps then read burunduk1's lecture note. (The Split and Rebuild variant)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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