KQUERY – SPOJ

Đề bài: http://vn.spoj.com/problems/KQUERY/

Thuật toán:

  • (đang cập nhập)

Code:

const   fi      ='';
        fo      ='';
        maxN    =300000;
        maxQ    =2*trunc(1e5);
 
type    arr1    =array[1..maxN] of longint;
var     n, q    :longint;
        a, csa  :arr1;
        x,y,k,csk,pos,kq   :arr1;
        T       :arr1;
 
Procedure hv(var a,b:longint);
var     tg      :longint;
begin
        tg:=a;a:=b;b:=tg;
end;
 
Procedure QS1(l,r:longint);
var     i, j, tg, xx    :longint;
begin
        i:=l;
        j:=r;
        xx:=a[(i+j) div 2];
        repeat
                while a[i]<xx do inc(i);
                while a[j]>xx do dec(j);
                if i<=j then
                        begin
                                hv(a[i],a[j]);
                                hv(csa[i],csa[j]);
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l<j then QS1(l,j);
        if i<r then QS1(i,r);
end;
 
Procedure QS2(l,r:longint);
var     i, j, tg, xx    :longint;
begin
        i:=l;
        j:=r;
        xx:=k[(i+j) div 2];
        repeat
                while k[i]<xx do inc(i);
                while k[j]>xx do dec(j);
                if i<=j then
                        begin
                                hv(k[i],k[j]);
                                hv(csk[i],csk[j]);
                                hv(x[i],x[j]);
                                hv(y[i],y[j]);
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l<j then QS2(l,j);
        if i<r then QS2(i,r);
end;
 
Procedure Update(x,v:longint);
begin
        while x<=maxn do
                begin
                        T[x]:=T[x]+v;
                        x:=x+x and (-x);
                end;
end;
 
Function Get(x:longint):longint;
begin
        Get:=0;
        while x>0 do
                begin
                        Get:=Get+t[x];
                        x:=x-x and (-x);
                end;
end;
 
Procedure xuly;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        csa[i]:=i;
                end;
        readln(q);
        for i:=1 to q do
                begin
                        readln(x[i],y[i],k[i]);
                        csk[i]:=i;
                end;
        QS1(1,n);
        QS2(1,q);
        for i:=1 to n do Update(i,1);
        j:=1;
        a[n+1]:=high(longint);
        for i:=1 to q do
                begin
                        while a[j]<=k[i] do
                                begin
                                        update(csa[j],-1);
                                        inc(j);
                                end;
                        if j<=n then
                                kq[csk[i]]:=Get(y[i])-Get(x[i]-1)
                        else kq[csk[i]]:=0;
                end;
        for i:=1 to q do writeln(kq[i]);
        close(input);close(output);
end;
 
begin
        xuly;
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

*