Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=50000;
var n,m,p,q,low,high,i:longint;
    a:array[1..maxn] of longint;
    min,max:array[1..maxn shl 2] of longint;

function getmin(x,y:longint):longint;
begin
     if x<y then getmin:=x else getmin:=y;
end;

function getmax(x,y:longint):longint;
begin
     if x>y then getmax:=x else getmax:=y;
end;

procedure initmax(node,l,r:longint);
var mid:longint;
begin
     if l=r then max[node]:=a[l]
     else
     begin
          mid:=(l+r) shr 1;
          initmax(node shl 1,l,mid);
          initmax(node shl 1+1,mid+1,r);
          max[node]:=getmax(max[node shl 1],max[node shl 1+1]);
     end;
end;

procedure initmin(node,l,r:longint);
var mid:longint;
begin
     if l=r then min[node]:=a[l]
     else
     begin
          mid:=(l+r) shr 1;
          initmin(node shl 1,l,mid);
          initmin(node shl 1+1,mid+1,r);
          min[node]:=getmin(min[node shl 1],min[node shl 1+1]);
     end;
end;

procedure findmin(node,l,r,p,q:longint);
var mid:longint;
begin
     if (l=p) and (r=q) then low:=getmin(low,min[node])
     else
     begin
          mid:=(l+r) shr 1;
          if p<=mid then findmin(node shl 1,l,mid,p,getmin(mid,q));
          if q>mid then findmin(node shl 1+1,mid+1,r,getmax(mid+1,p),q);
     end;
end;

procedure findmax(node,l,r,p,q:longint);
var mid:longint;
begin
     if (l=p) and (r=q) then high:=getmax(high,max[node])
     else
     begin
          mid:=(l+r) shr 1;
          if p<=mid then findmax(node shl 1,l,mid,p,getmin(mid,q));
          if q>mid then findmax(node shl 1+1,mid+1,r,getmax(mid+1,p),q);
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     readln(n,m);
     for i:=1 to n do readln(a[i]);
     initmin(1,1,n);
     initmax(1,1,n);
     for i:=1 to m do
     begin
          readln(p,q);
          low:=maxlongint;
          high:=-low;
          findmin(1,1,n,p,q);
          findmax(1,1,n,p,q);
          writeln(high-low);
     end;
     close(input);  close(output);
end.

Code mẫu của happyboy99x

#include <cstdio>
#include <cmath>

#define MAXN 50000+5
#define LOGMAXN 20 /*log 50000 ~ 16*/

int n, q;
int a[MAXN];
int m[MAXN][LOGMAXN], mx[MAXN][LOGMAXN];

int min( int a, int b ) { return a < b ? a : b; }
int max( int a, int b ) { return a>b?a:b; }

void preprocess() {
    for( int i = 0; i < n; m[i][0] = mx[i][0] = i, ++i ); 
    for( int j = 1; 1 << j <= n; ++j )
        for( int i = 0; i + ( 1 << j ) - 1 < n; ++i ) {
            m[i][j] = a[m[i][j-1]] < a[m[i+(1<<j-1)][j-1]] ? m[i][j-1] : m[i+(1<<j-1)][j-1];
            mx[i][j] = a[mx[i][j-1]] > a[mx[i+(1<<j-1)][j-1]] ? mx[i][j-1] : mx[i+(1<<(j-1))][j-1];
        }
}

int main() {
    scanf( "%d%d", &n, &q );
    for( int i = 0; i < n; scanf( "%d", &a[i++] ) );
    preprocess();
    for( int i = 0; i < q; ++i ) {
        int i, j, k; scanf( "%d%d", &i, &j ); --i; --j; k = (int) floor(log(j-i+1)/log(2));
        printf("%d\n", max(a[mx[i][k]], a[mx[j-(1<<k)+1][k]]) - min(a[m[i][k]], a[m[j-(1<<k)+1][k]]));
    }
    return 0;
}

Code mẫu của ladpro98

//http://vn.spoj.com/problems/NKLINEUP/
#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define mid (l + r >> 1)
#define left k + k
#define right left + 1
const int N = 50005;
const int oo = 1000000000;
using namespace std;
int n, q;

struct segment_tree {
    ii it[4 * N]; int n;
    segment_tree(int nn) {n = nn;}
    void Upd(int k, int l, int r, int i, int v) {
        if (l > r || i < l || r < i) return;
        if (l == r) {it[k].X = it[k].Y = v; return;}
        Upd(left, l, mid, i, v); Upd(right, mid + 1, r, i, v);
        it[k].X = max(it[left].X, it[right].X);
        it[k].Y = min(it[left].Y, it[right].Y);
    }
    ii Get(int k, int l, int r, int i, int j) {
        if (l > r || r < i || j < l) return ii(0, oo);
        if (i <= l && r <= j) return it[k];
        ii ll = Get(left, l, mid, i, j), rr = Get(right, mid + 1, r, i, j);
        return ii(max(ll.X, rr.X), min(ll.Y, rr.Y));
    }
    void Upd(int i, int v) {Upd(1, 1, n, i, v);}
    ii Get(int i, int j) {return Get(1, 1, n, i, j);}
};

int main()
{
    scanf("%d %d", &n, &q);
    int i, x, l, r; ii res;
    segment_tree IT (n);
    for(int i = 1; i <= n; i++) {scanf("%d", &x); IT.Upd(i, x);}
    while (q--) {
        scanf("%d %d", &l, &r);
        res = IT.Get(l, r);
        printf("%d\n", res.X - res.Y);
    }
    return 0;
}

Code mẫu của RR

uses math;
var
  a:array[1..50111] of longint;
  ln,nn:array[1..131072] of longint;
  n,q,i,u,v:longint;

procedure init(i,l,r:longint);
    var
      mid:longint;
    begin
      if l=r then
        begin
          ln[i]:=a[l];
          nn[i]:=a[l];
          exit;
        end;
      mid:=(l+r) shr 1;
      init(i shl 1,l,mid);
      init(i shl 1+1,mid+1,r);
      ln[i]:=max(ln[i shl 1],ln[i shl 1+1]);
      nn[i]:=min(nn[i shl 1],nn[i shl 1+1]);
    end;

function getMax(i,l,r,u,v:longint):longint;
    var
      mid:longint;
    begin
      if (v<l) or (r<u) then exit(-1);
      if (u<=l) and (r<=v) then exit(ln[i]);
      mid:=(l+r) shr 1;
      exit(max(getMax(i shl 1,l,mid,u,v),
               getMax(i shl 1+1,mid+1,r,u,v)));
    end;

function getMin(i,l,r,u,v:longint):longint;
    var
      mid:longint;
    begin
      if (v<l) or (r<u) then exit(1000111);
      if (u<=l) and (r<=v) then exit(nn[i]);
      mid:=(l+r) shr 1;
      exit(min(getMin(i shl 1,l,mid,u,v),
               getMin(i shl 1+1,mid+1,r,u,v)));
    end;

begin
  read(n,q);
  for i:=1 to n do
    read(a[i]);
  init(1,1,n);
  for i:=1 to q do
    begin
      read(u,v);
      writeln(getMax(1,1,n,u,v)-getMin(1,1,n,u,v));
    end;
end.

Code mẫu của hieult

#include <stdio.h>
#include <algorithm>
#include <cstring>
//#include <conio.h>
#define maxcao 1000000

using namespace std;

int f[300000],g[300000],a[50001],KQ1,KQ2;

void thietlap(int x,int y,int d)
{
     if(x==y){
         f[d]=a[x];
         g[d]=a[x];
     }
     else 
     {
          thietlap(x,(x+y)/2,2*d);
          thietlap((x+y)/2+1,y,2*d+1);
          f[d]=max(f[2*d],f[2*d+1]);
          g[d]=min(g[2*d],g[2*d+1]);
     }
}

void tinhmax(int dau,int cuoi,int x,int y,int d)
{
     if(dau>y||cuoi<x);
     else if(dau<=x&&cuoi>=y)
         KQ1=max(KQ1,f[d]);
     else
     {
         tinhmax(dau,cuoi,x,(x+y)/2,2*d);
         tinhmax(dau,cuoi,(x+y)/2+1,y,2*d+1);
     }
}

void tinhmin(int dau,int cuoi,int x,int y,int d)
{
     if(dau>y||cuoi<x);
     else if(dau<=x&&cuoi>=y)
         KQ2=min(KQ2,g[d]);
     else
     {
         tinhmin(dau,cuoi,x,(x+y)/2,2*d);
         tinhmin(dau,cuoi,(x+y)/2+1,y,2*d+1);
     }
}

int main()
{
     // freopen("NKLINEUP.in","r",stdin);
      int n,m,p,x,y,u;
      scanf("%d %d",&n,&m);
      for(int i=1;i<=n;i++)
      {     
           scanf("%d",&a[i]);
      }
      thietlap(1,n,1);
      for(int i=1;i<=m;i++)
      {
           scanf("%d %d",&x,&y);
           KQ1 = 0;KQ2 = maxcao;
           tinhmax(x,y,1,n,1);
           tinhmin(x,y,1,n,1);
           printf("%d\n",KQ1-KQ2);
      }
     // getch();
}

Code mẫu của ll931110

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.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   50505
int n,q;
int a,b;
int h[MAX];
int f[MAX][20];
int l[MAX][20];
int min(int x,int y) {
    if (x<y) return (x); else return (y);
}
int max(int x,int y) {
    if (x>y) return (x); else return (y);
}
void init(void) {
    scanf("%d",&n);
    scanf("%d",&q);
    int i;
    for (i=1;i<=n;i=i+1) scanf("%d",&h[i]);
}
void RMQ(void) {
    int i,j;
    for (i=1;i<=n;i=i+1) {
        f[i][0]=h[i];
        l[i][0]=h[i];
    }
    for (j=1;(1<<j)<=n;j=j+1)
        for (i=1;i+(1<<j)-1<=n;i=i+1) {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            l[i][j]=min(l[i][j-1],l[i+(1<<(j-1))][j-1]);
        }
}
int res(int a,int b) {
    int k=0;
    while ((1<<k)<=b-a+1) k=k+1;
    k=k-1;
    return (max(f[a][k],f[b-(1<<k)+1][k])-min(l[a][k],l[b-(1<<k)+1][k]));
}
void process(void) {
    int i;
    for (i=1;i<=q;i=i+1) {
        scanf("%d",&a);
        scanf("%d",&b);
        printf("%d\n",res(a,b));
    }
}
int main(void) {
    init();
    RMQ();
    process();
}

Code mẫu của khuc_tuan

uses math;
type integer = longint;
var
   i,ln, nn, u,v,n, q : integer;
   a : array[1..50000] of integer;
   ms, ml : array[1..4*50000] of integer;
   procedure init(node,l,r:integer);
   var
      mid : integer;
   begin
       if l=r then begin
           ms[node] := a[l];
           ml[node] := a[l];
       end
       else begin
           mid := (l+r) div 2;
           init(2*node,l,mid); init(2*node+1,mid+1,r);
           ms[node] := min( ms[2*node],ms[2*node+1]);
           ml[node] := max( ml[2*node],ml[2*node+1]);
       end;
   end;
   procedure get(node,l,r:integer);
   var mid : integer; begin
        if (u<=l) and (r<=v) then begin
            ln := max( ln, ml[node]);
            nn := min( nn, ms[node]);
            exit;
        end;
        mid := (l+r) div 2;
        if u<=mid then get(2*node,l,mid);
        if(mid<v) then get(2*node+1,mid+1,r);
   end;
begin
     read( n, q);
     for i:=1 to n do read(a[i]);
     init(1,1,n);
     for i:=1 to q do begin
         read(u,v);
         ln := 0;
         nn := 1000000000;
         get( 1, 1, n);
         writeln( ln-nn);
     end;
end.