不知怎地竟有种错觉此题最近做过= =目测是类似的？那道题貌似是纯动归？
本来今晚想做两道题的，一道是本题，一道是P1653疯狂的方格取数或NOI08 Employee，看看现在的时间目测这个目标又达不成了。
不过至少还是有收获的，虽然现在越来越觉得我做题的时间难以估摸了。
本来纯粹是以复习线段树（喂喂你本来就没码过几遍！）的心态来做这道题的，现在发现（1）我的基础好糟糕（2）这题其实不简单！
至今觉得我不用build_tree，直接维护树导致过程的参变很多这事儿有点麻烦，写个过程要传这么多变量，但是我又懒得去build_tree…
他们说这是区间DP，不管了反正我概念模糊的很凭感觉去做了，给我的感觉倒是和之前的树状DP有点像？选课那道题？（话说多叉转二叉还是挺有用的貌似~~）
updata子过程参考了vijos上的很多题解，话说这年头大神都用C++了，Pascal的解题也很少啊QAQ…最神的就是updata子过程，不得不佩服，把记录类型做参数传进去是平时很少用到的，但在这题中起到了很大的作用啊！
t[x]的字段sum表示总和，max表示这一段的最大区间，maxr表示带上右端点的max，maxl表示带上左端点的max。
鉴于这道题看了很多题解才做出来，有必要时不时拿出来温习，希望考试如果用到不要忘记了。
program vijos_p1083;
type keytype=record
sum,max,maxl,maxr:longint;
end;
var t:array[..] of keytype;
m,n,k,a,b,i:longint; procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end; function maxx(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure updata(var a:keytype;b,c:keytype); //神一般存在的过程
begin
a.sum:=b.sum+c.sum;
a.maxl:=maxx(b.maxl,b.sum+c.maxl);
a.maxr:=maxx(c.maxr,c.sum+b.maxr);
a.max:=maxx(b.max,c.max);
a.max:=maxx(a.max,b.maxr+c.maxl);
end; procedure change(now,left,right,loc,delta:longint);
var mid:longint;
begin
if (left=right) then
begin
t[now].sum:=delta;
t[now].maxl:=delta;
t[now].maxr:=delta;
t[now].max:=delta;
end
else
begin
mid:=(left+right) div ;
if loc>mid then change(now*+,mid+,right,loc,delta) else change(now*,left,mid,loc,delta);
updata(t[now],t[now*],t[now*+]);
end;
end; function work(now,left,right,a,b:longint):keytype;
var mid:longint;
begin
mid:=(left+right) div ;
if (a=left) and (b=right) then exit(t[now]); //此处的判断条件一开始写成了left=right，导致程序长跪不起一分钟也不出结果
if a>mid then exit(work(now*+,mid+,right,a,b));
if b<mid+ then exit(work(now*,left,mid,a,b));
updata(work,work(now*,left,mid,a,mid),work(now*+,mid+,right,mid+,b));
end; begin
readln(n,m);
for i:= to n do
begin
read(k);
change(,,n,i,k);
end;
for i:= to m do
begin
readln(k,a,b);
if (k=) and (a>b) then swap(a,b);
if k= then change(,,n,a,b) else writeln(work(,,n,a,b).max);
end;
end.
小白逛公园
P.S. 不知道为什么运行速度有点慢，我的in9在自己电脑上运行要4s左右，测评机上则是1.6s左右，难道该换电脑了？！
测试数据 #0: Accepted, time = 0 ms, mem = 32048 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 32044 KiB, score = 10
测试数据 #2: Accepted, time = 140 ms, mem = 32048 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 32044 KiB, score = 10
测试数据 #4: Accepted, time = 578 ms, mem = 32048 KiB, score = 10
测试数据 #5: Accepted, time = 1375 ms, mem = 32048 KiB, score = 10
测试数据 #6: Accepted, time = 1546 ms, mem = 32048 KiB, score = 10
测试数据 #7: Accepted, time = 1546 ms, mem = 32052 KiB, score = 10
测试数据 #8: Accepted, time = 1656 ms, mem = 32052 KiB, score = 10
测试数据 #9: Accepted, time = 1687 ms, mem = 32048 KiB, score = 10
Accepted, time = 8636 ms, mem = 32052 KiB, score = 100