NKINV – spoj

Đề bài

Thuật toán

  • Interval Tree

Code

uses    math;
const   fi='';
        fo='';
        maxn = 60000+3;
var     t       :array[1..maxn*4] of longint;
        i,j,n   :longint;
        a       :ARRAY[1..maxn] of longint;
        ma      :longint;
        res     :int64;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);for i:=1 to n do read(a[i]);
        close(input);
end;
procedure update(k,l,r,i:longint);
var     m :longint;
begin
        if (i<l) or (i>r) then exit;
        if l=r then
                begin
                        inc(t[k]);
                        exit;
                end;
        m := (l+r) div 2;
        update(k*2,l,m,i);
        update(k*2+1,m+1,r,i);
        t[k] := t[k*2] + t[k*2+1];
end;
function get(k,l,r,i,j:longint):longint;
var     m,tam1,tam2     :longint;
begin
        if i>j then exit(0);
        if (i>r) or (j<l) then exit(0);
        if (i<=l) and (j>=r) then
                begin
                        exit(t[k]);
                end;
        m := (l+r) div 2;
        tam1 := get(k*2,l,m,i,j);
        tam2 := get(k*2+1,m+1,r,i,j);
        get:= tam1+tam2;
end;
procedure process;
var     i :longint;
begin
        for i:=1 to n do ma := max(ma,a[i]);
        res := 0;
        for i:=1 to n do
                begin
                        res := res + get(1,1,ma,a[i]+1,ma);
                        update(1,1,ma,a[i]);
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Khuyên dùng

 

Speak Your Mind

*