Note: 本文最初于 2011年02月10日 星期四 19:20 在 hi.baidu.com/lydrainbowcat 发表。
题目大意：
给定n个有正有负的数，m个询问或修改，询问的格式为：闭区间[a,b]中连续的一段(该段长度可为在1~b-a+1之间任意长度，但必须连续)的最大值为多少；修改的格式为：把第x个数改成y。
算法思想：
线段树的记录数组 t 记录下来num、l、r、dat(区间最大值)、lmax(从左端开始的连续的一段的最大值)、rmax(从右端开始的连续的一段的最大值)、sum(区间和)。
建树（Build）和更改（Change）这样返回：
- t[num].sum:=t[num*2].sum+t[num*2+1].sum; //当前区间和等于左右子树区间和之和
- t[num].lmax:=max(t[num*2].lmax,t[num*2].sum+t[num*2+1].lmax); //从左端开始的连续一段的最大值可以是左子树上从左端开始的，也可以是整个左子树区间加上右子树上从左端开始的。
- t[num].rmax:=max(t[num*2+1].rmax,t[num*2+1].sum+t[num*2].rmax); //右端也是类似
- t[num].dat:=max(max(t[num*2].dat,t[num*2+1].dat),t[num*2].rmax+t[num*2+1].lmax);
//当前区间最大值可以是左右子树区间最大值， 也可能是左右子树中间一段连起来
询问（Ask）的返回也是类似，但是要判断左右子树是不是访问到了。比如没有询问左子树，那么右子树上的lmax也可以返回作为当前区间的lmax参考值。不要忘记给变量赋上初值（可以是-maxint）。
uses math; type rec=record l,r,dat,lmax,rmax,sum:longint; end; var t:array[0..1500000]of rec; n,m,i,k,x,y:longint; a:array[0..500000]of longint; procedure build(num,l,r:longint); var mid:longint; begin t[num].l:=l; t[num].r:=r; if l=r then begin t[num].dat:=a[l]; t[num].lmax:=a[l]; t[num].rmax:=a[l]; t[num].sum:=a[l]; exit; end; mid:=(l+r)div 2; build(num*2,l,mid); build(num*2+1,mid+1,r); t[num].sum:=t[num*2].sum+t[num*2+1].sum; t[num].lmax:=max(t[num*2].lmax,t[num*2].sum+t[num*2+1].lmax); t[num].rmax:=max(t[num*2+1].rmax,t[num*2+1].sum+t[num*2].rmax); t[num].dat:=max(max(t[num*2].dat,t[num*2+1].dat),t[num*2].rmax+t[num*2+1].lmax); end; function ask(num:longint):rec; var tl,tr:rec; mid:longint; visl,visr:boolean; begin if (x<=t[num].l)and(t[num].r<=y) then exit(t[num]); mid:=(t[num].l+t[num].r)shr 1; tl.sum:=-maxint; tr.sum:=-maxint; tl.dat:=-maxint; tr.dat:=-maxint; tl.lmax:=-maxint; tl.rmax:=-maxint; tr.lmax:=-maxint; tr.rmax:=-maxint; ask.sum:=0; visl:=false; visr:=false; if x<=mid then begin tl:=ask(num*2); inc(ask.sum,tl.sum); visl:=true; end; if y>mid then begin tr:=ask(num*2+1); inc(ask.sum,tr.sum); visr:=true; end; ask.dat:=max(max(tl.dat,tr.dat),tl.rmax+tr.lmax); ask.lmax:=max(tl.lmax,tl.sum+tr.lmax); if not visl then ask.lmax:=max(ask.lmax,tr.lmax); ask.rmax:=max(tr.rmax,tr.sum+tl.rmax); if not visr then ask.rmax:=max(ask.rmax,tl.rmax); end; procedure change(num:longint); var mid:longint; begin if (t[num].l=t[num].r)and(t[num].l=x) then begin t[num].dat:=y; t[num].lmax:=y; t[num].rmax:=y; t[num].sum:=y; exit; end; mid:=(t[num].l+t[num].r)div 2; if x<=mid then change(num*2); if x>mid then change(num*2+1); t[num].sum:=t[num*2].sum+t[num*2+1].sum; t[num].lmax:=max(t[num*2].lmax,t[num*2].sum+t[num*2+1].lmax); t[num].rmax:=max(t[num*2+1].rmax,t[num*2+1].sum+t[num*2].rmax); t[num].dat:=max(max(t[num*2].dat,t[num*2+1].dat),t[num*2].rmax+t[num*2+1].lmax); end; begin readln(n,m); for i:=1 to n do read(a[i]); build(1,1,n); for i:=1 to m do begin readln(k,x,y); case k of 1:begin if x>y then begin x:=x xor y; y:=x xor y; x:=x xor y; end; writeln(ask(1).dat); end; 2:change(1); end; end; end.