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.

Download