TyvjP1427小白逛公园 — 线段树任意区间“最大连续段”求法

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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注