NKLINEUP – spoj

Đề bài:

Thuật toán:

  • Interval tree

Code:

#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();
}
uses    math;
const   fi='';
        fo='';
        maxn=50000;
        maxq=200000;
type    arrp=record
                dau:longint;
                cuoi:longint;
                end;
var     i,j,n,q:longint;
        f:text;
        res1,res2:longint;
        a:array[1..maxn] of longint;
        p:array[1..maxq] of arrp;
        mind,maxd:array[1..maxn*4] of longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,q);
    for i:=1 to n do readln(f,a[i]);
    for i:=1 to q do readln(f,p[i].dau,p[i].cuoi);
    close(f);
end;
procedure update(k,l,r:longint);
var     mid:longint;
begin
    if l=r then
    begin
        maxd[k]:=a[l];
        mind[k]:=a[l];
    end
    else
    begin
        mid:=(l+r) div 2;
        update(k*2,l,mid);
        update(k*2+1,mid+1,r);
        mind[k]:=min(mind[k*2],mind[k*2+1]);
        maxd[k]:=max(maxd[k*2],maxd[k*2+1]);
    end;
end;
procedure find(k,l,r:longint);
var     mid:longint;
begin
    if (l>j) or (r<i) then exit;
    if (i<=l) and (j>=r) then
    begin
        res1:=min(res1,mind[k]);
        res2:=max(res2,maxd[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    find(k*2,l,mid);
    find(k*2+1,mid+1,r);
end;
procedure xuat;
var     k:longint;
begin
    assign(f,fo);
    rewrite(f);
    update(1,1,n);
    for k:=1 to q do
    begin
        res1:=high(longint);
        res2:=0;
        i:=p[k].dau;
        j:=p[k].cuoi;
        find(1,1,n);
        writeln(f,res2-res1);
    end;
    close(f);
end;
begin
    nhap;
    xuat;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*