学步园

有点区间dp的意思，用线段树记录区间的ans，st搞RMQ

f[x,y]=max{f[x,mid],f[mid+1,y],maxnum(mid+1,y)-minnum(x,mid)} 

我的code：

var
n,i,j,q,x,y:longint;
d,dd:array[1..400000,0..30] of longint;
l,r,v1,v2:array[1..1000000] of longint;

function max(a,b:longint):longint;
begin
if a>b then
  exit(a)
else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then
  exit(a)
else exit(b);
end;
function bg(x,y:longint):longint;
var k:longint;
begin
k:=trunc(ln(y-x+1)/ln(2));
exit(max(d[x,k],d[y-1 shl k+1,k]));
end;
function sm(x,y:longint):longint;
var k:longint;
begin
k:=trunc(ln(y-x+1)/ln(2));
exit(min(dd[x,k],dd[y-1 shl k+1,k]));
end;

{function f(x,y:longint):longint;
var ans,mid:longint;
begin
if x=y then
  exit(0);
mid:=(x+y) div 2;
ans:=max(f(x,mid),f(mid+1,y));
ans:=max(ans,bg(mid+1,y)-sm(x,mid));
exit(ans);
end;
function ff(x,y:longint):longint;
var ans,mid:longint;
begin
if x=y then
  exit(0);
mid:=(x+y) div 2;
ans:=max(ff(x,mid),ff(mid+1,y));
ans:=max(ans,bg(x,mid)-sm(mid+1,y));
exit(ans);
end;}

procedure build(p,x,y:longint);
var mid:longint;
begin
l[p]:=x;
r[p]:=y;
if x<>y then
begin
  mid:=(x+y) div 2;
  build(p*2,x,mid);
  build(p*2+1,mid+1,y);
  v1[p]:=max(v1[p*2],v1[p*2+1]);
  v1[p]:=max(v1[p],bg(mid+1,y)-sm(x,mid));
  v2[p]:=max(v2[p*2],v2[p*2+1]);
  v2[p]:=max(v2[p],bg(x,mid)-sm(mid+1,y));
end
else
begin
  v1[p]:=0;
  v2[p]:=0;
end;
end;

function f(p,x,y:longint):longint;
var mid:longint;
begin
if (l[p]=x)and(r[p]=y) then
  exit(v1[p]);
mid:=(l[p]+r[p]) div 2;
if y<=mid then
  exit(f(p*2,x,y));
if x>mid then
  exit(f(p*2+1,x,y));
f:=max(f(p*2,x,mid),f(p*2+1,mid+1,y));
f:=max(f,bg(mid+1,y)-sm(x,mid));
end;

function ff(p,x,y:longint):longint;
var mid:longint;
begin
if (l[p]=x)and(r[p]=y) then
  exit(v2[p]);
mid:=(l[p]+r[p]) div 2;
if y<=mid then
  exit(ff(p*2,x,y));
if x>mid then
  exit(ff(p*2+1,x,y));
ff:=max(ff(p*2,x,mid),ff(p*2+1,mid+1,y));
ff:=max(ff,bg(x,mid)-sm(mid+1,y));
end;

begin
readln(n);
for i:=1 to n do
begin
  read(d[i,0]);
  dd[i,0]:=d[i,0];
end;
for j:=1 to trunc(ln(n)/ln(2)) do
  for i:=1 to n-1 shl j+1 do
  begin
    d[i,j]:=max(d[i,j-1],d[i+1 shl (j-1),j-1]);
    dd[i,j]:=min(dd[i,j-1],dd[i+1 shl (j-1),j-1]);
  end;
build(1,1,n);

readln(q);
for i:=1 to q do
begin
  readln(x,y);
  if x<=y then
    writeln(f(1,x,y))
  else writeln(ff(1,y,x));
end;
end.