学步园

【题意】

有n个数序列s，求出满足s[i]<s[k]<s[j](i<k<j,j>=i+1)的最大j-i的值

【输入】

多组数据

每组数据第一行为n

第二行为n个数，描述s

【输出】

对于每组数据输出最大的j-i的值

可以转化为rmq问题

枚举i，可以通过二分找到满足之间最小数大于p[i]的最右端i`

然后又可以找到i+1到i`之间的最大值k

然后再通过二分查找最靠左的值为k的位置

program poj2452;
type
  arr=array [0..16,0..50001] of longint;
var
  n,i,j,k,s,e,ans,mid:longint;
  p:array [0..50001] of longint;
  max,min:arr;

function wmax (a,b:longint;var max:arr;x:longint):longint;
var
  k:longint;
begin
  if a=b then exit(p[a]);
  k:=trunc(ln(b-a+1)/ln(2));
  if max[k,a]*x>max[k,b-(1 shl k)+1]*x then exit(max[k,a])
                                       else exit(max[k,b-(1 shl k)+1]);
end;

procedure st (var max:arr;x:longint);
begin
  for i:=1 to n do
    max[0,i]:=p[i];
  k:=0;
  while 1 shl k<n do
    begin
      for i:=1 to n do
        if i+(1 shl k)>n then max[k+1,i]:=max[k,i]
                         else
        if max[k,i]*x>max[k,i+(1 shl k)]*x then max[k+1,i]:=max[k,i]
                                           else max[k+1,i]:=max[k,i+(1 shl k)];
      inc(k);
    end;
end;

begin
  while not seekeof do
    begin
      read(n);
      for i:=1 to n do
        read(p[i]);
      if n<=1 then
        begin
          writeln(-1);
          continue;
        end;
      st(max,1);
      st(min,-1);
      ans:=0;
      for i:=1 to n-1 do
        begin
          if p[i+1]<=p[i] then continue;
          s:=i+1;
          e:=n;
          while s<>e do
            begin
              mid:=s+e-(s+e) div 2;
              if wmax(i+1,mid,min,-1)>p[i] then s:=mid
                                           else e:=mid-1;
            end;
          k:=wmax(i+1,s,max,1);
          if p[i+1]=k then
            begin
              if ans<1 then ans:=1;
              continue;
            end;
          s:=i+2;
          while s<>e do
            begin
              mid:=s+e-(s+e) div 2;
              if wmax(i+1,mid-1,max,1)<k then s:=mid
                                         else e:=mid-1;
            end;
          if e-i>ans then ans:=e-i;
        end;
      if ans=0 then writeln(-1)
               else writeln(ans);
    end;
end.