NKLINEUP - Xếp hàng
Tác giả: ll931110
Ngôn ngữ: Pascal
Program NKLINEUP;
Const
input = '';
output = '';
Var
a: array[1..50000] of longint;
f1,f2,d1,d2: array[1..300000] of longint;
n,q: longint;
r1,r2,dau,cuoi: longint;
fi,fo: text;
Procedure enter;
Var
i: longint;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi, n, q);
For i:= 1 to n do readln(fi, a[i]);
End;
Function max(x,y: longint): longint;
Begin
If x > y then max:= x else max:= y;
End;
Function min(x,y: longint): longint;
Begin
If x < y then min:= x else min:= y;
End;
Procedure swap(x,y: longint);
Var
tmp: longint;
Begin
tmp:= x;
x:= y;
y:= tmp;
End;
Procedure build1(k, L, H: longint);
Var
mid: longint;
Begin
If L > H then exit;
If L = H then
Begin
f1[k]:= a[L];
exit;
End;
mid:= (L + H) div 2;
build1(2 * k, L, mid);
build1(2 * k + 1, mid + 1, H);
f1[k]:= max(f1[2 * k],f1[2 * k + 1]);
End;
Procedure build2(k, L, H: longint);
Var
mid: longint;
Begin
If L > H then exit;
If L = H then
Begin
f2[k]:= a[L];
exit;
End;
mid:= (L + H) div 2;
build2(2 * k, L, mid);
build2(2 * k + 1, mid + 1, H);
f2[k]:= min(f2[2 * k],f2[2 * k + 1]);
End;
Procedure visit1(k, L, H: longint);
Var
mid: longint;
Begin
If (L > cuoi) or (dau > H) then exit;
If (dau <= L) and (H <= cuoi) then
Begin
r1:= max(r1,f1[k]);
exit;
End;
mid:= (L + H) div 2;
visit1(2 * k, L, mid);
visit1(2 * k + 1, mid + 1, H);
End;
Procedure visit2(k, L, H: longint);
Var
mid: longint;
Begin
If (L > cuoi) or (dau > H) then exit;
If (dau <= L) and (H <= cuoi) then
Begin
r2:= min(r2,f2[k]);
exit;
End;
mid:= (L + H) div 2;
visit2(2 * k, L, mid);
visit2(2 * k + 1, mid + 1, H);
End;
Procedure solve;
Var
i,u,v,res: longint;
Begin
Assign(fo, output);
Rewrite(fo);
build1(1,1,n);
build2(1,1,n);
For i:= 1 to q do
Begin
Readln(fi, u, v);
If u > v then swap(u,v);
r1:= 0;
r2:= maxlongint;
If u = v then writeln(fo, 0)
else if abs(u - v) = 1 then
writeln(fo, abs(a[u] - a[v]))
else
Begin
dau:= u;
cuoi:= v;
visit1(1,1,n);
visit2(1,1,n);
res:= r1 - r2;
Writeln(fo, res);
End;
End;
Close(fo);
Close(fi);
End;
Begin
enter;
solve;
End.