不超过 k 段的最大子序列和

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定整数序列 $a_1,a_2,\ldots,a_n$，处理以下两类操作：

• 0 i val：令 $a_i=val$；
• 1 l r k：在 $a_l,\ldots,a_r$ 中选择不超过 $k$ 个两两不相交的非空连续子段，最大化这些子段内元素之和并输出最大值。

可以一个子段也不选，因此查询答案至少为 $0$。

输入格式

第一行一个整数 $n$。第二行包含 $n$ 个整数 $a_i$。

第三行一个整数 $m$。接下来 $m$ 行，每行是一条上述操作。

输出格式

对每条类型为 1 的操作输出一行答案。

样例输入 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\le n,m\le10^5$，$|a_i|,|val|\le500$，$1\le k\le20$；类型为 1 的操作不超过 $10000$ 次。所有下标与查询区间均合法。

每个测试点独立计分。