DQUERY - D-query
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
//{$APPTYPE CONSOLE}
{$mode delphi}
type
integer = longint;
var
n : integer;
ind, value, a : array[1..30000] of integer;
pos : array[1..1000000] of integer;
q : integer;
oo, aind, ai, aj, ak : array[1..200000] of integer;
bit : array[1..30000] of integer;
procedure sort1(l,r : integer);
var
x, t : integer;
i, j : integer;
begin
if l>=r then exit;
i := l;
j := r;
x := ind[(l+r) div 2];
repeat
while a[ind[i]] > a[x] do inc(i);
while a[ind[j]] < a[x] do dec(j);
if i<=j then
begin
t := ind[i];
ind[i] := ind[j];
ind[j] := t;
inc(i);
dec(j);
end;
until i>j;
sort1(i,r);
sort1(l,j);
end;
procedure sort2(l,r : integer);
var
i, j : integer;
x, t : integer;
begin
if l>r then exit;
i := l;
j := r;
x := ak[(l+r) div 2];
repeat
while ak[i]>x do inc(i);
while ak[j]<x do dec(j);
if i<=j then
begin
t := ak[i]; ak[i] := ak[j]; ak[j] := t;
t := ai[i]; ai[i] := ai[j]; ai[j] := t;
t := aj[i]; aj[i] := aj[j]; aj[j] := t;
t := aind[i]; aind[i] := aind[j]; aind[j] := t;
inc(i);
dec(j);
end;
until i>j;
sort2(i,r);
sort2(l,j);
end;
function getsum(i : integer) : integer;
var
r : integer;
begin
r := 0;
while i>0 do
begin
inc(r, bit[i]);
i := i and (i-1);
end;
getsum := r;
end;
var
st, i, j : integer;
begin
read(n);
for i:=1 to n do
begin
read(value[i]);
ind[i] := i;
end;
for i:=1 to 1000000 do pos[i] := n + 1;
for i:=n downto 1 do
begin
a[i] := pos[value[i]];
pos[value[i]] := i;
end;
read(q);
for i:=1 to q do
begin
read(ai[i], aj[i]);
ak[i] := aj[i];
aind[i] := i;
end;
sort1(1,n);
sort2(1,q);
st := 1;
for i:=1 to q do
begin
while (st<=n) and (a[ind[st]]>ak[i]) do
begin
// update ind[st]
j := ind[st];
while j<=n do
begin
inc(bit[j]);
inc(j, j and (-j));
end;
inc(st);
end;
oo[aind[i]] := getsum(aj[i]) - getsum(ai[i]-1);
end;
for i:=1 to q do writeln(oo[i]);
// readln; readln; readln;
end.