DQUERY - D-query

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program DQUERY;
const
  input  = '';
  output = '';
  maxn = 30010;
  maxk = 200010;
  maxv = 1000000;
type
  pnode = ^tnode;
  tnode = record
    val: integer;
    next: pnode;
  end;
var
  p,res: array[1..2 * maxk] of integer;
  v: array[1..maxv] of integer;
  a,t: array[1..maxn] of integer;
  link: array[1..maxn] of pnode;
  n,k: integer;
  fi,fo: text;

// Analyze: Create new array {s} satisfying
// s[i] = max j | (j < i) and (s[j] = s[i]). s[i] = 0 if there doesn't exist j
// Using KQUERY: query(i,j) equals to the number of integers in the subsequence [i,j] which is less than i

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure add(i,x: integer);
var
  q: pnode;
begin
  if i = 0 then exit;
  new(q);
  q^.val := x;
  q^.next := link[i];
  link[i] := q;
end;

procedure init;
var
  i,num: integer;
begin
  readln(fi, n);
  fillchar(v, sizeof(v), 0);
  for i := 1 to n do
    begin
      read(fi, num);
      a[i] := v[num];
      v[num] := i;
    end;

  readln(fi, k);
  for i := 1 to k do
    begin
      read(fi, p[2 * i]);
      add(p[2 * i] - 1,2 * i);

      read(fi, p[2 * i + 1]);
      add(p[2 * i + 1],2 * i + 1);

      v[i] := p[2 * i];
    end;

end;

// BIT operations

procedure update(x: integer);
begin
  while x <= maxn do
    begin
      inc(t[x]);
      x := x + (x and -x);
    end;
end;

function calc(x: integer): integer;
var
  r: integer;
begin
  r := 0;
  while x > 0 do
    begin
      r := r + t[x];
      x := x - (x and -x);
    end;
  calc := r;
end;

// End of BIT operations

procedure solve;
var
  i,tmp: integer;
  s: pnode;
begin
  fillchar(t, sizeof(t), 0);
  fillchar(res, sizeof(res), 0);

  for i := 1 to n do
    begin
      update(a[i] + 1);
      s := link[i];
      while s <> nil do
        begin
          tmp := s^.val;
          res[tmp] := calc(v[tmp div 2]);
          s := s^.next;
        end;
    end;

  for i := 1 to k do writeln(fo, res[2 * i + 1] - res[2 * i]);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

begin
  openfile;
  init;
  solve;
  closefile;
end.

Download