Zgg吃东西
时间限制：10s 空间限制：256MB
题目描述
Zgg是一个吃货。他面前有一堆的食品。不妨把它看成一个序列，序列从1~N编号，第i个位置上有美味度为A[i]的食品。Zgg有很多只手(为什么他有这么多手？我也不知道)。他的手的作用，就是抓起一段连续序列中的食物，并且不限长度。总共有M个时刻，在每个时刻，可能会有一些奇怪的人将他面前的某一个位置的食物美味度改变。或者zgg突然心血来潮，想要用他的其中k只手来抓取某段区间中的食物。这时候，他就需要你告诉他，在用不超过k只手的情况下，他能获得的最大美味度是多少。
输入格式
第一行一个整数N，表示食品的个数，即序列长度。
第2行有N个数依次表示A[i]。
第三行一个整数M，表示有M个时刻。
接下来的M行，每行有形如0 i val
来表示有人将第i位置的食物的美味度改成了val
或者1 l r k，来表示zgg想知道，他只用k只手，在[l,r]这段区间内抓取，能获得的最大美味度。
输出格式
对于每次形如1 l r k的询问你都要输出一个数，表示最大美味度。
样例输入
9 9 -8 9 -1 -1 -1 9 -8 9 5 1 1 9 1 1 1 9 2 1 4 6 3 0 3 -8 1 1 9 1
样例输出
17 25 0 10
提示
对于100%的数据 N,M<=100000 ,1<=k<=20.l<=l<=r<=n.数值的绝对值不会超过500.
Zgg是可以有手空闲的…
题目来源
没有写明来源