FIRS - Hàng cây

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program FIRS;
uses math;
const
  input  = '';
  output = '';
  maxn = 100000;
  maxv = 10000000;
type
  rec = record
    val,pos: integer;
  end;
var
  a: array[1..maxn] of integer;
  s: array[1..8 * maxn] of rec;
  n,res,u,v: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do read(f, a[i]);

  close(f);

  for i := 1 to 8 * maxn do s[i].val := maxv;
end;

procedure combine(i: integer);
begin
  s[i].val := min(s[2 * i].val,s[2 * i + 1].val);
  if s[2 * i + 1].val < s[2 * i].val then s[i].pos := s[2 * i + 1].pos
                                     else s[i].pos := s[2 * i].pos;
end;

procedure build(i,low,high: integer);
var
  mid: integer;
begin
  if low > high then exit;
  if low = high then
    begin
      s[i].val := a[low];
      s[i].pos := low;
      exit;
    end;

  mid := (low + high) div 2;
  build(2 * i,low,mid);
  build(2 * i + 1,mid + 1,high);
  combine(i);
end;

procedure update(i,low,high: integer);
var
  mid: integer;
begin
  if (v < low) or (high < u) then exit;
  if s[i].val = maxv then exit;

  if (u <= low) and (high <= v) then
    begin
      s[i].val := maxv;
      s[i].pos := 0;
      exit;
    end;

  mid := (low + high) div 2;
  update(2 * i,low,mid);
  update(2 * i + 1,mid + 1,high);
  combine(i);
end;

procedure solve;
var
  t: integer;
begin
  res := 0;
  repeat
    t := s[1].pos;
    if t <> 0 then
      begin
        inc(res);
        u := t - 1;
        v := t + 1;

        if t = 1 then u := 1
        else if t = n then v := n;

        update(1,1,n);
      end;
  until s[1].pos = 0;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  build(1,1,n);
  solve;
  printresult;
end.

Download