NKLINEUP spoj - Xếp hàng - Kiến Thức 24h

Nguồn đề bài: http://vn.spoj.com/problems/NKLINEUP/

1. Đề bài BCLINEUP spoj PTIT

Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 50000) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao.
Bác John đã chuẩn bị một danh sách gồm Q (1 ≤ Q ≤ 200000) đoạn các con bò và chiều cao của chúng (trong phạm vi [1, 1000000]). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này!

Dữ liệu

Dòng đầu tiên chứa 2 số nguyên N và Q.
Dòng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ i.
Dòng thứ i trong số Q trong tiếp theo chứa 2 số nguyên A, B (1 ≤ A ≤ B ≤ N), cho biết đoạn các con bò từ A đến B.

Kết quả

Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng.

Ví dụ

Dữ liệu:
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Kết qủa
6
3
0

2. Hướng dẫn BCLINEUP spoj

Bài này nếu bạn nào rành về cây Interval Tree bài cơ bản sẽ hiểu cách để giải bài này. bài này đơn giản chỉ là xây dựng cùng lúc 2 cây IT, một cây tìm min và 1 cây tìm max và lấy độ chênh lệch giữa min và max là dc. bạn có thể tham khảo code sau:

3. code tham khảo BCLINEUP spoj (Pascal, C++):

a. Code pascal

uses    math;
const   fi='';
        nmax=50001;
type    data=longint;

var
        f:text;
        Tmin,Tmax,A:array[0..nmax*5] of data;
        N,Q:data;

procedure napdulieu(i,l,r:data);
var     mid:data;
begin
        if l=r then
                begin
                        Tmin[i]:=A[L];
                        Tmax[i]:=A[L];
                        exit;
                end;
        mid:=(l+r) div 2;
        napdulieu(i*2,l,mid);
        napdulieu(i*2+1,mid+1,r);
        Tmin[i]:=min(Tmin[i*2],tmin[i*2+1]);
        tmax[i]:=max(tmax[i*2],tmax[i*2+1]);
end;

procedure minmax(i,l,r,u,v:data; var gtmin,gtmax:data);
var     mid,maxtrai,mintrai,maxphai,minphai:data;
begin
        if (l=u) and (r=v) then
                begin
                        gtmin:=Tmin[i];
                        gtmax:=tmax[i];
                        exit;
                end;
        if (v<l) or (r<u) then
                begin
                        gtmin:=high(data);
                        gtmax:=0;
                        exit;
                end;
        mid:=(l+r) div 2;
        minmax(i*2,   l    , mid  ,u,min(v,mid) ,mintrai,maxtrai);
        minmax(i*2+1, mid+1, r    ,max(mid+1,u),v ,minphai,maxphai);
        gtmin:=min(mintrai,minphai);
        gtmax:=max(maxtrai,maxphai);
end;


procedure xuli;
var     i,u,v,gtmin,gtmax:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,q);
        for i:=1 to n do
                readln(f,a[i]);
        napdulieu(1,1,n);
        for i:=1 to q do
                begin
                        readln(f,u,v);
                        minmax(1,1,n,u,v,gtmin,gtmax);
                        writeln(abs(gtmin-gtmax));
                end;


        close(f);
end;


begin
        xuli;
end.

b. Code c++

#include <bits/stdc++.h>
using namespace std;

int n,q;
vector<int> a;
vector< pair<int,int> > node;
int resmax, resmin;

void Init_Tree(int k, int l, int r, int i)
{
    if(l>i || r<i) return;
    if(l==r)
    {
        node[k]=make_pair(a[i],a[i]);
        return;
    }
    int m=(l+r)/2;
    Init_Tree(2*k,l,m,i);
    Init_Tree(2*k+1,m+1,r,i);
    node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
}

void Init()
{
    scanf("%d%d",&n,&q);
    a.resize(n+2);
    node.resize(4*n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Init_Tree(1,1,n,i);
    }
}

void Query(int k, int l, int r, int A, int B)
{
    if(l>B || r<A) return;
    if(A<=l && B>=r)
    {
        resmax=max(resmax,node[k].first);
        resmin=min(resmin,node[k].second);
        return;
    }
    int m=(l+r)/2;
    Query(2*k,l,m,A,B);
    Query(2*k+1,m+1,r,A,B);
}

void Solve()
{
    for (int i=1;i<=q;i++)
    {
        int A, B;
        scanf("%d%d",&A,&B);
        resmax=0;
        resmin=10000000;
        Query(1,1,n,A,B);
        printf("%dn",resmax-resmin);
    }
}

int main()
{
    Init();
    Solve();
}

[/sociallocker]

NKLINEUP spoj – Xếp hàng