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 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 lxx 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 l0 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.