DQUERY - D-query
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
const
FINP='';
FOUT='';
MAXN=30011;
MAXQ=200011;
var
n,q:longint;
ind,a,pre,count:array[0..MAXN] of longint;
now:array[1..1000000] of longint;
inq,kq,x,y:array[0..MAXQ] of longint;
procedure inp;
var
f:text;
i:longint;
begin
assign(f,FINP); reset(f);
read(f,n);
for i:=1 to n do read(f,a[i]);
read(f,q);
for i:=1 to q do read(f,x[i],y[i]);
close(f);
end;
procedure ans;
var
f:text;
i:longint;
begin
assign(f,FOUT); rewrite(f);
for i:=1 to q do
writeln(f,kq[i]);
close(f);
end;
procedure swap(var a,b:longint); inline;
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
var mid,mid2:longint;
procedure sortQ(l,r:longint); inline;
var
i,j:longint;
begin
i:=l; j:=r;
mid:=x[l+random(r-l+1)];
repeat
while x[i]<mid do inc(i);
while x[j]>mid do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
swap(inq[i],inq[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sortQ(i,r);
if l<j then sortQ(l,j);
end;
procedure sortD(l,r:longint); inline;
var
i,j:longint;
begin
i:=l; j:=r; mid:=pre[l+random(r-l+1)];
repeat
while pre[i]<mid do inc(i);
while pre[j]>mid do dec(j);
if i<=j then
begin
swap(pre[i],pre[j]);
swap(ind[i],ind[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sortD(i,r);
if l<j then sortD(l,j);
end;
procedure update(u:longint); inline;
var
v:longint;
begin
inc(count[u]);
v:=u+u and (-u);
if v<=n then update(v);
end;
function get(u:longint):longint; inline;
var
v,kq:longint;
begin
if u=0 then exit(0);
kq:=count[u];
v:=u-u and (-u);
if v>0 then inc(kq,get(v));
get:=kq;
end;
procedure solve;
var
i,luu:longint;
begin
for i:=1 to q do inq[i]:=i;
sortQ(1,q);
now[a[1]]:=1;
for i:=2 to n do
begin
pre[i]:=now[a[i]];
now[a[i]]:=i;
end;
for i:=1 to n do ind[i]:=i;
sortD(1,n);
luu:=1; pre[n+1]:=MAXN+1;
for i:=1 to q do
begin
while (pre[luu]<x[i]) do
begin
update(ind[luu]);
inc(luu);
end;
kq[inq[i]]:=get(y[i])-get(x[i]-1);
end;
end;
begin
inp;
solve;
ans;
end.