CF280D k-Maximum Subsequence Sum

Consider integer sequence $ a_{1},a_{2},...,a_{n} $ . You should run queries of two types: - The query format is " $ 0 $ $ i $ $ val $ ". In reply to this query you should make the following assignment: $ a_{i}=val $ . - The query format is " $ 1 $ $ l $ $ r $ $ k $ ". In reply to this query you should print the maximum sum of at most $ k $ non-intersecting subsegments of sequence $ a_{l},a_{l+1},...,a_{r} $ . Formally, you should choose at most $ k $ pairs of integers $ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{t},y_{t}) $ $ (l

N/A

N/A

In the first query of the first example you can select a single pair $ (1,9) $ . So the described sum will be 17. Look at the second query of the first example. How to choose two subsegments? (1, 3) and (7, 9)? Definitely not, the sum we could get from (1, 3) and (7, 9) is 20, against the optimal configuration (1, 7) and (9, 9) with 25. The answer to the third query is 0, we prefer select nothing if all of the numbers in the given interval are negative.