题目

题目描述

给定整数序列 $a_{1}, a_{2}, ..., a_{n}$。你需要处理两种类型的查询：

1. 查询格式为 “$0\ i\ val$”。对于该查询，你需要进行如下赋值操作：$a_{i}=val$。
2. 查询格式为 “$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 \lt x_2 \leq y_2 \lt ... \lt 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$ 个互不相交子段最大和的查询，输出其最大和。按输入顺序输出每个查询的答案。