← 返回题目列表

Codeforces · 280/D

D. k-最大子序列和

中文机器翻译题面 查看原题

考虑整数序列 a1, a2, ..., an。您应该运行两种类型的查询:

- 查询格式为“0 i val”。为了回复此查询,您应该进行以下分配:ai = val。
- 查询格式为“1 l r k”。为了回答这个查询,你应该打印序列 al, al + 1, ..., ar 的至多 k 个不相交子段的最大总和。形式上,您应该最多选择 k 对整数 (x1, y1), (x2, y2), ..., (xt, yt) (l ≤ x1 ≤ y1 < x2 ≤ y2 < ... < xt ≤ yt ≤ r; t ≤ k) 使得总和ax1 + ax1 + 1 + ... + ay1 + ax2 + ax2 + 1 + ... + ay2 + ... + axt + axt + 1 + ... + ayt尽可能大。请注意,您最多应选择 k 个子段。特别是,您可以选择 0 个子段。在这种情况下,所描述的总和被认为等于零。

输入

第一行包含整数 n (1 ≤ n ≤ 105),显示序列有多少个数字。下一行包含 n 个整数 a1, a2, ..., an (|ai| ≤ 500)。

第三行包含整数 m (1 ≤ m ≤ 105) — 查询数量。接下来的 m 行包含语句中给出的格式的查询。

所有更改的查询都符合限制:1 ≤ i ≤ n,|val| ≤ 500。

所有计算最多 k 个不相交子段的最大和的查询均满足以下限制:1 ≤ l ≤ r ≤ n、1 ≤ k ≤ 20。保证计算最多 k 个不相交子段的最大和的查询数量不超过 10000。

输出

对于每个查询,计算最多 k 个不相交子段的最大总和,打印回复 - 最大总和。按顺序打印查询的答案,其中查询位于输入后面。

示例

输入 #1

9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3

输出 #1

17
25
0

输入 #2

15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1

输出 #2

14
11
15
0
15
26
18
23
8

注意

在第一个示例的第一个查询中,您可以选择单个对 (1, 9)。因此所描述的总和将为 17。

查看第一个示例的第二个查询。如何选择两个子段? (1, 3) 和 (7, 9)?绝对不是,我们从 (1, 3) 和 (7, 9) 得到的总和是 20,而最佳配置 (1, 7) 和 (9, 9) 的总和是 25。

第三个查询的答案是 0,如果给定区间内的所有数字都是负数,我们宁愿不选择任何内容。