All Tracks>Data Structures> Advanced Data Structures> Segment Trees> Problem
Reversing elements
★★★★★

3.3

3 votes
Abstract class, Advanced Data Structures, Data Structures, Hard, Segment Trees, maximum sub array sum, oct circuits
Problem

You are given an arrayA of size N and Q queries. For each query, you are given two indices of the array L and R. The subarray generated from L to R is reversed. Your task is to determine the maximum sum of the subarrays.

Note: After each query is solved, the array comes to its initial states.

Input format

  • First line: Two space-separated integers N and Q
  • Next line: N space-separated integers denoting the array elements.
  • Next Q lines: Two space-separated integers in every line denoting the values of Liand Ri

Output format

For each query, print the required answer in a new line.

Constraints

  • 1≤N,Q≤105
  • 1≤L≤R≤N
  • −106≤Ai≤106
Sample Input
5 2
3 -1 4 2 -1
3 4
1 2
Sample Output
8
9
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Given array is {3,-1,4,2,-1}.

For first query L=3 and R=4. Now the array becomes {3,-1,2,4,-1}.

Maximum sub-array sum is 8 and the sub-array is {3,-1,2,4}.

For second query L=1 and R=2. Now the array becomes {-1,3,4,2,-1}.

Maximum sub-array sum is 9 and the sub-array is {3,4,2}.

Contributers:
Editor Image

?