KC采花
时间限制：30s 空间限制：256MB
题目描述
KC在公园里种了一排花，一共有n朵，游手好闲的KC常常在公园里采花。他对每朵花都有一个美丽度鉴赏。由于对花的喜好不同，有的花分数很高，有的花分数很低，甚至会是负数。
KC很忙，每次采花的时候，不可能从第一朵花，走到第n朵。所以他会先选定一个区间[l,r](1<=l<=r<=n)，作为当天的采花范围。同时为了方便采花，他总是从[l,r]中最多选出k个互不相交的子区间，将这些子区间的花全部采光。当然，他希望美丽度总和最大。
KC对花的鉴赏随着他对世界观人生观的改变而改变，他会不时地对每朵花的美丽度进行修改，可能改低，也可能提高。
KC的行为持续m天，每天的行为要么是采花，要么是改变花的美丽度。
注：(1)[l,r]的最多k个互不相同子区间可以表示成：[x1,y1],[x2,y2],...,[xt,yt]，满足l<=x1<=y1<x2<=y2<...<xt<=yt<=r，且0<=t<=k。
(2)由于是KC种的花，一朵花采掉第二天会立刻生出来。
输入格式
第一行一个正整数n,n<=100000。
第二行n个整数a1,a2...an，表示n朵花的美丽度。|ai|<=500。
第三行一个正整数m,m<=100000。
第四行开始，接下来m行，每行表示该天KC的行为。
修改美丽度的行为用0 i val描述，表示将ai修改为val,|val|<=500。
采花行为用1 l r k描述,k<=20意义如题面。
输出格式
对于每个采花行为，每行一个整数表示最大的美丽度总和。
样例输入
9 9 -8 9 -1 -1 -1 9 -8 9 3 1 1 9 1 1 1 9 2 1 4 6 3
样例输出
17 25 0
提示
100%的数据，满足n,m<=50000,k<=20,ai以及修改的val的绝对值不超过500。
题目来源
最大费用最大流