CF280D k-Maximum Subsequence Sum

给定整数序列 $a_{1}, a_{2}, ..., a_{n}$。你需要处理两种类型的查询： - 查询格式为 “$0\ i\ val$”。对于该查询，你需要进行如下赋值操作：$a_{i}=val$。 - 查询格式为 “$1\ l\ r\ k$”。对于该查询，你需要输出从序列 $a_{l},a_{l+1},...,a_{r}$ 中选取不超过 $k$ 个互不相交的子段所能获得的最大和。形式化地说，你可以选择不超过 $k$ 个整数对 $(x_1, y_1), (x_2, y_2), ..., (x_t, y_t)$，满足 $l \leq x_1 \leq y_1 < x_2 \leq y_2 < ... < x_t \leq y_t \leq r, t \leq k$，使得和 $a_{x_1} + a_{x_1+1} + ... + a_{y_1} + a_{x_2} + a_{x_2+1} + ... + a_{y_2} + ... + a_{x_t} + a_{x_t+1} + ... + a_{y_t}$ 达到最大。注意，你最多可以选择 $k$ 个子段，特别地，你也可以一个都不选，此时和为 0。

第一行一个整数 $n$，表示序列中数字的个数，$1 \leq n \leq 10^{5}$。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$，$|a_i| \leq 500$。 第三行一个整数 $m$，表示查询数量，$1 \leq m \leq 10^{5}$。 接下来的 $m$ 行，每行表示一个查询，格式见描述。 所有赋值操作保证 $1 \leq i \leq n$，$|val| \leq 500$。 所有区间和最大和查询保证 $1 \leq l \leq r \leq n$，$1 \leq k \leq 20$。 保证所有区间和最大和查询的总数不超过 $10000$。

对于每一个求不超过 $k$ 个互不相交子段最大和的查询，输出其最大和。按输入顺序输出每个查询的答案。

在第一个样例的第一个查询中，可以选择一对 $(1,9)$，此时总和为 17。 来看第一个样例的第二个查询。如何选择两个子段？$(1,3)$ 和 $(7,9)$？这样得到的和是 20，但最优解是 $(1,7)$ 和 $(9,9)$，和为 25。 第三个查询答案为 0。如果给定区间内所有数均为负数，选择不选任何子段更优，和为 0。 由 ChatGPT 5 翻译