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 ≤ _x_1 ≤ _y_1 < _x_2 ≤ _y_2 < ... < x__t ≤ y__t ≤ r; t ≤ k) such that the sum _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 is as large as possible. Note that you should choose at most k subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero.

考虑整数序列 $a_1, a_2, \dots, a_n$。你需要处理两类查询：

• 查询格式为 "0 i val"。对于该查询，你需要执行如下赋值操作：$a_i = \text{val}$。
• 查询格式为 "1 l r k"。对于该查询，你需要输出序列 $a_l, a_{l+1}, \dots, a_r$ 中至多 $k$ 个互不相交子段的最大和。形式上，你需要选择至多 $k$ 对整数 $(x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)$，满足

  $$l \le x_1 \le y_1 < x_2 \le y_2 < \dots < x_t \le y_t \le r,\quad t \le k,$$

  使得和

  $$a_{x_1} + a_{x_1+1} + \dots + a_{y_1} + a_{x_2} + a_{x_2+1} + \dots + a_{y_2} + \dots + a_{x_t} + a_{x_t+1} + \dots + a_{y_t}$$

  尽可能大。注意你最多只能选择 $k$ 个子段；特别地，你可以选择 $0$ 个子段，此时上述和定义为 $0$。

The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers the sequence has. The next line contains n integers _a_1, _a_2, ..., a__n (|a__i| ≤ 500).

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries. The next m lines contain the queries in the format, given in the statement.

All changing queries fit into limits: 1 ≤ i ≤ n, |val| ≤ 500.

All queries to count the maximum sum of at most k non-intersecting subsegments fit into limits: 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20. It is guaranteed that the number of the queries to count the maximum sum of at most k non-intersecting subsegments doesn't exceed 10000.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示序列中数字的个数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \leq 500$）。

第三行包含一个整数 $m$（$1 \leq m \leq 10^5$），表示查询的个数。接下来的 $m$ 行包含题目描述中所给格式的查询。

所有修改类查询均满足如下限制：$1 \leq i \leq n$，$|val| \leq 500$。

所有计算区间 $[l, r]$ 内至多 $k$ 个互不相交子区间的最大和的查询均满足如下限制：$1 \leq l \leq r \leq n$，$1 \leq k \leq 20$。保证此类查询的总数不超过 $10000$。

For each query to count the maximum sum of at most k non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.

对于每个查询（计算最多 k 个互不相交子区间的最大和），输出对应的答案——该最大和。请按照输入中查询出现的顺序输出各查询的答案。

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.

在第一个例子的第一个查询中，你可以选择唯一一对子段 $(1,\ 9)$。因此，所描述的和为 $17$。

观察第一个例子的第二个查询：如何选择两个子段？$(1,\ 3)$ 和 $(7,\ 9)$？显然不行，从 $(1,\ 3)$ 和 $(7,\ 9)$ 得到的和为 $20$，而最优配置 $(1,\ 7)$ 和 $(9,\ 9)$ 对应的和为 $25$。

第三个查询的答案是 $0$：如果给定区间内的所有数均为负数，我们宁愿不选任何子段。