UNTITLE1 - Untitled Problem II
You are given a sequence of N integers A1, A2 ... AN. (-10000 <= Ai <= 10000, N <= 50000)
Let Si denote the sum of A1 ... Ai. You need to apply M (M <= 50000) operations:
- 0 x y k: increase all integers from Ax to Ay by k (1 <= x <= y <= N, -10000 <= k <= 10000).
- 1 x y: ask for max{ Si | x <= i <= y }.(1 <= x <= y <= N)
Input
- In the first line there is an integer N.
- The following line contains N integers that represent the sequence.
- The third line contains an integer M denotes the number of operations.
- In the next M lines, each line contains an operation "0 x y k" or "1 x y".
Output
For each "1 x y" operation, print one integer representing its result.
Example
Input: 5 238 -9622 5181 202 -6943 5 1 3 4 0 5 5 4846 1 3 5 0 3 5 -7471 1 3 3 Output: -4001 -4001 -11674
Use signed 64-bit integer :)
hide comments
[Rampage] Blue.Mary:
2010-02-04 09:43:31
A little constant optimization is needed. Last edit: 2010-02-04 09:43:49 |
|
Matt Garman:
2009-09-02 21:09:05
Are the operations cumulative? Or is the sequence "reset" back to original after ever "1 x y" operation? |
|
Ivan Katanic:
2009-08-20 17:22:23
Increase an consecutive interval[x,y]. |
|
piyifan:
2009-06-29 01:41:45
what does increase all integers from Ax to Ay by k mean?Incease an consecutive interval[x,y] or increase all integer big than Ax and less than Ay. |
Added by: | Qu Jun |
Date: | 2008-08-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Not an own problem |