简单题，每次取出最长链，然后对于练上每个点x，终点在其子树内的链都要减去a[x]
这显然可以用dfs序+线段树维护
显然每个点只要删一次即可，复杂度是O(nlogn)
type node=record
s,lx,rx,mx,lp,rp,pb,pe:longint;
end; var tree:array[..*,..] of node;
rev:array[..*] of boolean;
a:array[..] of longint;
q:array[..] of node;
j,t,ans,i,n,m,x,y,k,ch:longint;
c:node; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; procedure put(var a:node; x:longint);
begin
a.lx:=x;
a.rx:=x;
a.mx:=x;
a.s:=x;
end; procedure update(var c:node; a,b:node);
begin
c.s:=a.s+b.s;
c.lx:=a.lx; c.lp:=a.lp;
if a.s+b.lx>c.lx then
begin
c.lx:=a.s+b.lx;
c.lp:=b.lp;
end;
c.rx:=b.rx; c.rp:=b.rp;
if b.s+a.rx>c.rx then
begin
c.rx:=b.s+a.rx;
c.rp:=a.rp;
end; c.mx:=a.rx+b.lx; c.pb:=a.rp; c.pe:=b.lp;
if c.mx<a.mx then
begin
c.mx:=a.mx;
c.pb:=a.pb;
c.pe:=a.pe;
end;
if c.mx<b.mx then
begin
c.mx:=b.mx;
c.pb:=b.pb;
c.pe:=b.pe;
end;
end; procedure build(i,l,r:longint);
var m,j:longint;
begin
if l=r then
begin
put(tree[i,],a[l]);
put(tree[i,],-a[l]);
for j:= to do
begin
tree[i,j].lp:=l;
tree[i,j].rp:=l;
tree[i,j].pb:=l;
tree[i,j].pe:=l;
end;
end
else begin
m:=(l+r) shr ;
build(i*,l,m);
build(i*+,m+,r);
update(tree[i,],tree[i*,],tree[i*+,]);
update(tree[i,],tree[i*,],tree[i*+,]);
end;
end; procedure change(i:longint);
begin
swap(tree[i,],tree[i,]);
rev[i]:=not rev[i];
end; procedure push(i:longint);
begin
rev[i]:=false;
change(i*);
change(i*+);
end; procedure work(i,l,r:longint);
var m:longint;
begin
if l=r then
begin
put(tree[i,],y);
put(tree[i,],-y);
end
else begin
m:=(l+r) shr ;
if rev[i] then push(i);
if x<=m then work(i*,l,m)
else work(i*+,m+,r);
update(tree[i,],tree[i*,],tree[i*+,]);
update(tree[i,],tree[i*,],tree[i*+,]);
end;
end; function ask(i,l,r:longint):node;
var m:longint;
s,s1,s2:node;
begin
if (x<=l) and (y>=r) then exit(tree[i,])
else begin
m:=(l+r) shr ;
if rev[i] then push(i);
if y<=m then exit(ask(i*,l,m));
if x>m then exit(ask(i*+,m+,r));
s1:=ask(i*,l,m);
s2:=ask(i*+,m+,r);
update(s,s1,s2);
exit(s);
end;
end; procedure rever(i,l,r,x,y:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then change(i)
else begin
m:=(l+r) shr ;
if rev[i] then push(i);
if x<=m then rever(i*,l,m,x,y);
if y>m then rever(i*+,m+,r,x,y);
update(tree[i,],tree[i*,],tree[i*+,]);
update(tree[i,],tree[i*,],tree[i*+,]);
end;
end; begin
readln(n);
for i:= to n do
read(a[i]);
build(,,n);
readln(m);
for i:= to m do
begin
read(ch);
if ch= then
begin
readln(x,y,k);
ans:=;
t:=;
for j:= to k do
begin
c:=ask(,,n);
if c.mx> then ans:=ans+c.mx
else break;
rever(,,n,c.pb,c.pe);
inc(t);
q[t]:=c;
end;
for j:=t downto do
rever(,,n,q[j].pb,q[j].pe);
writeln(ans);
end
else begin
readln(x,y);
work(,,n);
end;
end;
end.