对于这样的问题，分操作考虑。第一个操作，显然可以直接单点修改，修改的过程与我们需要维护的信息有关，暂先不管；注意到问题的核心在于第二个操作怎么解决。
首先将这个询问拆出来，简化成为这样一个问题：
对于一个序列 (a)，选 (k) 个不相交的子段和的最大值是多少？
假设现在我们贪心选了最大的子段，这一段需要被拿出去。但是显然我们可以不选两个正数段里面的负数算，这样的贪心显然是错误的。
考虑反悔贪心。我们需要一个方法将这个取走的数的贡献通过另一种方法去掉。既然之前是正贡献，那么显然这里就要变成负贡献。于是这里选出来的子段和全部乘上 (-1)，然后继续找。发现这样如果再选到取负的值，相当于没有选，每次拓展还可以使选出来的段数增加 (1)（如果选相交了，发现刚好可以拆开成为两段；否则不相交使直接两段）。对于这个问题只需要拓展 (k) 次即可。注意可以不选，所以说当已经不能使贡献增加时就可以不选了。
需要维护区间最大最小子段和（最小子段和可以理解成乘 (-1) 之后两者交换），显然可以用线段树去维护。当这个段被选掉之后乘上 (-1) 可以将最大最小子段和取负交换即可。操作的时候还需要额外维护最大最小子段和，左边界最大最小子段和，右边界最大最小子段和的区间编号信息。
至于将线段树还原，可以记录修改了哪些段，再暴力修改回来即可。时间复杂度 (O(mk log n))。细节很多。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define lc(x) (x<<1)
#define rc(x) ((x<<1)|1)
#define Mm int mid=(l+r)>>1
int n;
LL a[100005];
struct node{
LL lmax,rmax,maxn,sum;
int l,r,ll,lr,rl,rr;
node(LL LM=0,LL RM=0,LL M=0,LL S=0,int L=0,int R=0,int Ll=0,int LR=0,int RL=0,int RR=0){lmax=LM,rmax=RM,maxn=M,sum=S,l=L,r=R,ll=Ll,lr=LR,rl=RL,rr=RR;}
}tr[400005],minn[400005];
bool tag[400005];
LL read()
{
LL x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x*f;
}
void push_up(int now)
{
tr[now].sum=tr[lc(now)].sum+tr[rc(now)].sum;
tr[now].lmax=max(tr[lc(now)].lmax,tr[lc(now)].sum+tr[rc(now)].lmax);
if(tr[now].lmax==tr[lc(now)].lmax) tr[now].ll=tr[lc(now)].ll,tr[now].lr=tr[lc(now)].lr;
else tr[now].ll=tr[lc(now)].ll,tr[now].lr=tr[rc(now)].lr;
tr[now].rmax=max(tr[rc(now)].rmax,tr[rc(now)].sum+tr[lc(now)].rmax);
if(tr[now].rmax==tr[rc(now)].rmax) tr[now].rl=tr[rc(now)].rl,tr[now].rr=tr[rc(now)].rr;
else tr[now].rl=tr[lc(now)].rl,tr[now].rr=tr[rc(now)].rr;
tr[now].maxn=max(max(tr[lc(now)].maxn,tr[rc(now)].maxn),tr[lc(now)].rmax+tr[rc(now)].lmax);
if(tr[now].maxn==tr[lc(now)].maxn) tr[now].l=tr[lc(now)].l,tr[now].r=tr[lc(now)].r;
else if(tr[now].maxn==tr[rc(now)].maxn) tr[now].l=tr[rc(now)].l,tr[now].r=tr[rc(now)].r;
else tr[now].l=tr[lc(now)].rl,tr[now].r=tr[rc(now)].lr;
minn[now].sum=minn[lc(now)].sum+minn[rc(now)].sum;
minn[now].lmax=min(minn[lc(now)].lmax,minn[lc(now)].sum+minn[rc(now)].lmax);
if(minn[now].lmax==minn[lc(now)].lmax) minn[now].ll=minn[lc(now)].ll,minn[now].lr=minn[lc(now)].lr;
else minn[now].ll=minn[lc(now)].ll,minn[now].lr=minn[rc(now)].lr;
minn[now].rmax=min(minn[rc(now)].rmax,minn[rc(now)].sum+minn[lc(now)].rmax);
if(minn[now].rmax==minn[rc(now)].rmax) minn[now].rl=minn[rc(now)].rl,minn[now].rr=minn[rc(now)].rr;
else minn[now].rl=minn[lc(now)].rl,minn[now].rr=minn[rc(now)].rr;
minn[now].maxn=min(min(minn[lc(now)].maxn,minn[rc(now)].maxn),minn[lc(now)].rmax+minn[rc(now)].lmax);
if(minn[now].maxn==minn[lc(now)].maxn) minn[now].l=minn[lc(now)].l,minn[now].r=minn[lc(now)].r;
else if(minn[now].maxn==minn[rc(now)].maxn) minn[now].l=minn[rc(now)].l,minn[now].r=minn[rc(now)].r;
else minn[now].l=minn[lc(now)].rl,minn[now].r=minn[rc(now)].lr;
}
void build(int l,int r,int now)
{
if(l==r)
{
minn[now]=tr[now]=node(a[l],a[l],a[l],a[l],l,l,l,l,l,l);
return ;
}
Mm;
build(l,mid,lc(now));
build(mid+1,r,rc(now));
push_up(now);
}
void changeNode(int now)
{
tr[now].lmax=-tr[now].lmax;
tr[now].rmax=-tr[now].rmax;
tr[now].maxn=-tr[now].maxn;
tr[now].sum=-tr[now].sum;
minn[now].lmax=-minn[now].lmax;
minn[now].rmax=-minn[now].rmax;
minn[now].maxn=-minn[now].maxn;
minn[now].sum=-minn[now].sum;
swap(tr[now],minn[now]);
}
void push_down(int now)
{
if(tag[now])
{
tag[lc(now)]=!tag[lc(now)];
tag[rc(now)]=!tag[rc(now)];
changeNode(lc(now));
changeNode(rc(now));
tag[now]=false;
}
}
void modify(int l,int r,int x,int y,int now)
{
if(x<=l && r<=y)
{
tag[now]=!tag[now];
changeNode(now);
return ;
}
push_down(now);
Mm;
if(x<=mid) modify(l,mid,x,y,lc(now));
if(mid<y) modify(mid+1,r,x,y,rc(now));
push_up(now);
}
void modifyPoint(int l,int r,int x,int now,int val)
{
if(l==r)
{
minn[now]=tr[now]=node(val,val,val,val,l,l,l,l,l,l);
return ;
}
push_down(now);
Mm;
if(x<=mid) modifyPoint(l,mid,x,lc(now),val);
else modifyPoint(mid+1,r,x,rc(now),val);
push_up(now);
}
node query(int l,int r,int now,int x,int y)
{
if(x<=l && r<=y) return tr[now];
Mm;
push_down(now);
if(x<=mid && mid>=y) return query(l,mid,lc(now),x,y);
if(mid<y && x>mid) return query(mid+1,r,rc(now),x,y);
node que1=query(l,mid,lc(now),x,y),que2=query(mid+1,r,rc(now),x,y),que3;
que3.sum=que1.sum+que2.sum;
que3.lmax=max(que1.lmax,que1.sum+que2.lmax);
que3.rmax=max(que2.rmax,que2.sum+que1.rmax);
que3.maxn=max(max(que1.maxn,que2.maxn),que1.rmax+que2.lmax);
if(que3.lmax==que1.lmax) que3.ll=que1.ll,que3.lr=que1.lr;
else que3.ll=que1.ll,que3.lr=que2.lr;
if(que3.rmax==que2.rmax) que3.rl=que2.rl,que3.rr=que2.rr;
else que3.rl=que1.rl,que3.rr=que2.rr;
if(que3.maxn==que1.maxn) que3.l=que1.l,que3.r=que1.r;
else if(que3.maxn==que2.maxn) que3.l=que2.l,que3.r=que2.r;
else que3.l=que1.rl,que3.r=que2.lr;
return que3;
}
int st[25],su[25],top;
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
build(1,n,1);
int m=read();
while(m-->0)
{
int op=read();
if(!op)
{
int x=read(),val=read();
modifyPoint(1,n,x,1,val);
}
else
{
int l=read(),r=read(),k=read();
LL ans=0;
for(int i=1;i<=k;++i)
{
node s=query(1,n,1,l,r);
if(s.maxn<=0) break;
ans+=s.maxn;
++top;
st[top]=s.l;
su[top]=s.r;
modify(1,n,s.l,s.r,1);
}
printf("%lld
",ans);
while(top) modify(1,n,st[top],su[top],1),--top;
}
}
return 0;
}