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.

Download