DMOPC '16 Contest 3 P6 - Long Lost Love

View as PDF
Submit solution
Points: 17 (partial)
Time limit: 0.75s
Memory limit: 200M
Authors:
Phoenix1369, WallE256
Problem type

Recently Phoenix1369 revisited his long lost love, Segment Tree Test. After a long battle with his feelings, he realized he could no longer keep them bottled up.

After many sleepless nights of browsing the internet, he finally came up with the problem. However, try as he might, the solution of the problem did not meet his standards, nor did they meet those of the other contestants.

Being extremely persistent, Phoenix1369 has decided to try once more in projecting his emotions onto his problems. Please free him from the burden of his emotions by answering the following queries:

  • U pos val - Change the value from position pos to value val.
  • G x - Revert to revision x.
  • P x y - Output the maximum prefix sum on the interval from x to y.
  • S x y - Output the maximum suffix sum on the interval from x to y.

At this point in time, WallE256 came along to make sure everything is going according to plan, and mentioned that a revision is created when you receive a structure-changing query (G and U). The initial structure has the revision index 0.

Input Specification

On the first line of input you will find the integer N (1 \le N \le 100\,000), representing the size of the array.
On the second line of input you will find N space-separated integers, representing the initial array. It is guaranteed that the total sum of the given numbers does not exceed 2^{31}-1.
On the third line of input, you will find the integer Q (1 \le Q \le 500\,000), representing the number of queries.
On the next Q lines of input, you will find queries formatted as specified above.

Output Specification

For each of the P and S queries, output its result on a single line by itself in order according to the input.

Sample Input

5
-1 -2 -3 -2 9
5
P 2 3
U 1 8
S 1 5
G 0
S 1 5

Sample Output

-2
10
9

Comments


  • 3
    MouhebBoucherb  commented on Dec. 15, 2016, 9:53 a.m.

    the array is indexed from 0 to N-1 or from 1 to N


    • 2
      WallE256  commented on Dec. 15, 2016, 4:42 p.m.

      The array is 1 indexed.