type gotree=record
       l,r,m,nm,nl,nr:longint;
      end;
var
  tree:array[1..400000]of gotree;
  a2,a3,b2,b3:longint;
  a:array[1..100000]of longint;
  i,n,m,x,y,ans,fly:longint;
procedure maketree(t,l,r,k,v:longint);
  var
    mid:longint;
  begin
    mid:=(l+r)shr 1;
    if (r=l)and(mid=l)then
      begin
       tree[t].l:=1;
       tree[t].r:=1;
       tree[t].m:=1;
       tree[t].nm:=v;
       tree[t].nl:=v;
       tree[t].nr:=v;
       exit;
      end;
    if mid>=k then
      maketree(t+t,l,mid,k,v)
     else
      maketree(t+t+1,mid+1,r,k,v);
//tree[t].n
    tree[t].m:=tree[t+t].m;
    tree[t].nm:=tree[t+t].nm;
    if tree[t].m<tree[t+t+1].m then
      begin
       tree[t].m:=tree[t+t+1].m;
       tree[t].nm:=tree[t+t+1].nm;
      end;
    if tree[t+t].nr=tree[t+t+1].nl then
      begin
       tree[t].nm:=tree[t+t].nr;
       tree[t].m:=tree[t+t].r+tree[t+t+1].l;
      end;
    if tree[t+t].l>tree[t].m then
      begin
       tree[t].m:=tree[t+t].l;
       tree[t].nm:=tree[t+t].nl;
      end;
    if tree[t+t+1].r>tree[t].m then
      begin
       tree[t].m:=tree[t+t+1].r;
       tree[t].nm:=tree[t+t+1].nr;
      end;
//tree[t].l
    if tree[t+t].nl=tree[t+t+1].nl then
      begin
       tree[t].l:=tree[t+t].l+tree[t+t+1].l;
       tree[t].nl:=tree[t+t].nl;
      end
     else
      begin
       tree[t].l:=tree[t+t].l;
       tree[t].nl:=tree[t+t].nl;
      end;
//tree[t].r
    tree[t].nr:=tree[t+t+1].nr;
    if tree[t+t].nr=tree[t+t+1].nr then
      begin
       tree[t].r:=tree[t+t].r+tree[t+t+1].r;
      end
     else
      begin
       tree[t].r:=tree[t+t+1].r;
      end;
  end;
procedure hunt(t,l,r,ll,rr:longint);
  var
    mid:longint;
  begin
    if (ll<=l)and(rr>=r) then
      begin
       if a2=-10000000 then
         begin
          ans:=tree[t].l;
          a3:=tree[t].r;
          a2:=tree[t].m;
          b3:=tree[t].nr;
          b2:=tree[t].nm;
         end
        else
         begin
          if b2=tree[t].nl then a2:=a2+tree[t].l;
          if a2<tree[t].m then begin b2:=tree[t].nm; a2:=tree[t].m;end;
          if (b3=tree[t].nl)and(ans<a3+tree[t].l) then ans:=a3+tree[t].l;
          if tree[t].nr=b3 then a3:=a3+tree[t].r else
            begin
             a3:=tree[t].r;
             b3:=tree[t].nr;
            end;
         end;
       exit;
      end;
    if l=r then exit;
    mid:=(l+r)shr 1;
    if ll<=mid then hunt(t+t,l,mid,ll,rr);
    if rr>mid then hunt(t+t+1,mid+1,r,ll,rr);
  end;
begin
read(n);
while n<>0 do
begin
 fillchar(tree,sizeof(tree),0);
 readln(m);
 for i:=1 to n do
   begin
    read(a[i]);
    maketree(1,1,n,i,a[i]);
   end;
 for i:=1 to m do
   begin
    read(x,y);
    a2:=-10000000;a3:=0;b2:=0;b3:=0;
    hunt(1,1,n,x,y);
    if ans<a2 then ans:=a2;
    if ans<a3 then ans:=a3;
    writeln(ans);
   end;
read(n);
end;
end.

• Re:拍了很多次都对的 为什么还会wrong (59) xuhaoran510 2010-11-28 08:51:13
  • Re:拍了很多次都对的 为什么还会wrong (89) andone 2010-12-04 01:04:23