ORDERSET - Order statistic set

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program ORDERSET;
const
  input  = '';
  output = '';
  maxn = 200000;
var
  a,b,pos,list,t: array[1..maxn] of integer;
  ch: array[1..maxn] of char;
  q,num,c1: integer;
  fi,fo: text;

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

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


//Pre-processing

procedure init;
var
  i: integer;
begin
  c1 := 0;
  readln(fi, q);
  for i := 1 to q do
    begin
      read(fi, ch[i]);
      if ch[i] = 'K' then readln(fi, a[i]) else
        begin
          inc(c1);
          readln(fi, b[c1]);
          pos[c1] := i;
        end;
    end;
end;

procedure swap(var x,y: integer);
var
  z: integer;
begin
  z := x;  x := y; y := z;
end;

procedure swapint(i,j: integer);
begin
  swap(b[i],b[j]);
  swap(pos[i],pos[j]);
end;

procedure quicksort;

  procedure par(l,h: integer);
  var
    i,j,p: integer;
  begin
    if l >= h then exit;
    i := l;  j := h;  p := b[random(h - l + 1) + l];

    repeat
      while b[i] < p do inc(i);
      while b[j] > p do dec(j);

      if i <= j then
        begin
          if i < j then swapint(i,j);
          inc(i);
          dec(j);
        end;
    until i > j;

    par(l,j);
    par(i,h);
  end;

var
  i: integer;
begin
  if c1 = 0 then exit;
  par(1,c1);

  num := 1;
  a[pos[1]] := 1;
  list[1] := b[1];

  for i := 2 to c1 do
    begin
      if b[i] > b[i - 1] then
        begin
          inc(num);
          list[num] := b[i];
        end;
      a[pos[i]] := num;
    end;
end;

//End of pre-processing



//BIT's operations

procedure update(x,k: integer);
begin
  while x <= maxn do
    begin
      t[x] := t[x] + k;
      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's operations



//Query's operations

procedure insert(x: integer);
begin
  if calc(x) = calc(x - 1) then update(x,1);
end;

procedure delete(x: integer);
begin
  if calc(x) > calc(x - 1) then update(x,-1);
end;

procedure kth(x: integer);
var
  inf,sup,mid: integer;
  res,tmp: integer;
begin
  if calc(num) < x then
    begin
      writeln(fo, 'invalid');
      exit;
    end;

  inf := 1;
  sup := num;

  repeat
    mid := (inf + sup) div 2;

    tmp := calc(mid);
    if tmp = x then
      begin
        res := mid;
        if tmp = calc(mid - 1) then sup := mid - 1 else break;
      end
    else if tmp < x then inf := mid + 1
    else
      begin
        res := mid;
        sup := mid - 1;
      end;
  until inf > sup;

  writeln(fo, list[res]);
end;

procedure count(x: integer);
begin
  writeln(fo, calc(x - 1));
end;

//End of query's operations



//Answer
procedure solve;
var
  i: integer;
begin
  fillchar(t, sizeof(t), 0);
  for i := 1 to q do
    case ch[i] of
      'I': insert(a[i]);
      'D': delete(a[i]);
      'K': kth(a[i]);
      'C': count(a[i]);
    end;
end;



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



begin
  openfile;
  init;
  quicksort;
  solve;
  closefile;
end.

Download