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是可以有手空闲的…


题目来源

没有写明来源