好题，这道题可以用线段树来快速模拟费用流寻找最长增广路
这样修改怎么做也很显然了
1 type node=record 2 s,lx,rx,mx,lp,rp,pb,pe:longint; 3 end; 4 5 var tree:array[0..100010*4,0..1] of node; 6 rev:array[0..100010*4] of boolean; 7 a:array[0..100010] of longint; 8 q:array[0..100010] of node; 9 j,t,ans,i,n,m,x,y,k,ch:longint; 10 c:node; 11 12 procedure swap(var a,b:node); 13 var c:node; 14 begin 15 c:=a; 16 a:=b; 17 b:=c; 18 end; 19 20 procedure put(var a:node; x:longint); 21 begin 22 a.lx:=x; 23 a.rx:=x; 24 a.mx:=x; 25 a.s:=x; 26 end; 27 28 procedure update(var c:node; a,b:node); 29 begin 30 c.s:=a.s+b.s; 31 c.lx:=a.lx; c.lp:=a.lp; 32 if a.s+b.lx>c.lx then 33 begin 34 c.lx:=a.s+b.lx; 35 c.lp:=b.lp; 36 end; 37 c.rx:=b.rx; c.rp:=b.rp; 38 if b.s+a.rx>c.rx then 39 begin 40 c.rx:=b.s+a.rx; 41 c.rp:=a.rp; 42 end; 43 44 c.mx:=a.rx+b.lx; c.pb:=a.rp; c.pe:=b.lp; //这里要维护位置，相当于记录增广路的起点终点 45 if c.mx=r) then exit(tree[i,1])119 else begin120 m:=(l+r) shr 1;121 if rev[i] then push(i);122 if y<=m then exit(ask(i*2,l,m));123 if x>m then exit(ask(i*2+1,m+1,r));124 s1:=ask(i*2,l,m);125 s2:=ask(i*2+1,m+1,r);126 update(s,s1,s2);127 exit(s);128 end;129 end;130 131 procedure rever(i,l,r,x,y:longint); //翻转，因为图的特殊性可知132 var m:longint;133 begin134 if (x<=l) and (y>=r) then change(i)135 else begin136 m:=(l+r) shr 1;137 if rev[i] then push(i);138 if x<=m then rever(i*2,l,m,x,y);139 if y>m then rever(i*2+1,m+1,r,x,y);140 update(tree[i,1],tree[i*2,1],tree[i*2+1,1]);141 update(tree[i,0],tree[i*2,0],tree[i*2+1,0]);142 end;143 end;144 145 begin146 readln(n);147 for i:=1 to n do148 read(a[i]);149 build(1,1,n);150 readln(m);151 for i:=1 to m do152 begin153 read(ch);154 if ch=1 then155 begin156 readln(x,y,k);157 ans:=0;158 t:=0;159 for j:=1 to k do160 begin161 c:=ask(1,1,n);162 if c.mx>0 then ans:=ans+c.mx163 else break;164 rever(1,1,n,c.pb,c.pe);165 inc(t);166 q[t]:=c;167 end;168 for j:=t downto 1 do169 rever(1,1,n,q[j].pb,q[j].pe);170 writeln(ans);171 end172 else begin173 readln(x,y);174 work(1,1,n);175 end;176 end;177 end.