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.

Download