FOCUS - Chuyên gia ruồi

Tác giả: RR

Ngôn ngữ: Pascal

{$IFDEF NORMAL}
  {$H-,I+,OBJECTCHECKS-,Q+,R+,S+}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
  {$H-,I+,OBJECTCHECKS-,Q+,R+,S+}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
  {$H-,I-,OBJECTCHECKS-,Q-,R-,S-}
{$ENDIF RELEASE}
uses math;
const
  fin ='';
  fout='';
  maxquest=222222;
  maxage=maxquest;

type
  quest_data=record ch:char; x,y,z:longint end;
  it_tree=array[0..maxage*4] of longint;

var
  fi,fo:text;
  nage:longint;
  age:array[0..maxage] of longint;
  pos_age:array[0..maxage] of longint;
  real_age:array[0..maxage] of longint;
  que:array[0..maxquest] of quest_data;
  nque:longint;
  it:it_tree;
  left,right,res,count:longint;

procedure enter;
  var
    i:longint;
  begin
    readln(Fi,nque);
    for i:=1 to nque do
      begin
        read(Fi,que[i].ch);
        case que[i].ch of
          '+','-': readln(fi,que[i].x);
          '?':readln(fi,que[i].x,que[i].y,que[i].z);
        end;
      end;
  end;

procedure init;
  begin
    filldword(it,sizeof(it) div 4,0);
  end;

procedure make_age;
  var
    i:longint;
  begin
    nage := 0;
    for i:=1 to nque do
      begin
        if (que[i].ch = '+') or (que[i].ch = '-') then
          begin
            inc(nage);
            age[nage] := que[i].x;
            pos_age[nage] := i;
          end;
      end;
  end;

procedure swap(var x,y:longint);
  var
    tg:longint;
  begin
    tg:=x;
    x:=y;
    y:=tg;
  end;

procedure quicksort(l,h:longint);
  var
    i,j,pivot:longint;
  begin
    if l >= h then exit;
    i := l;
    j := h;
    pivot := age[random(h-l+1) + l];

    repeat
      while age[i] < pivot do inc(i);
      while age[j] > pivot do dec(j);
      if i <= j then
        begin
          swap(age[i],age[j]);
          swap(pos_age[i],pos_age[j]);
          inc(i);
          dec(J);
        end;
    until i > j;

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

procedure roirac_age;
  var
    i,nn:longint;
  begin
    quicksort(1,nage);

    nn:=1;
    real_age[1] := age[1];
    que[pos_age[1]].x := 1;

    for i:=2 to nage do
      if age[i] > age[i-1] then
        begin
          inc(nn);
          real_age[nn] := age[i];
          que[pos_age[i]].x := nn;
        end
      else que[pos_age[i]].x := nn;

    nage := nn;
  end;

procedure update(k,l,h,x,val:longint);
  var
    mid:longint;
  begin
    if (l > h) or (l > x) or (h < x) then exit;
    if (l = h) then
      begin
        if l = x then it[k] := it[k] + val;
        exit;
      end;

    mid := (l+h) div 2;

    update(k*2,l,mid,x,val);
    update(k*2+1,mid+1,h,x,val);

    it[k] := it[k*2] + it[k*2+1];
  end;

procedure get(k,l,h:longint);
  var
    mid:longint;
  begin
    if (res <> 0) or (l > h) or (left > right)
      or (real_age[h] < left) or (real_age[l] > right) then exit;

    mid := (l+h) div 2;

    if (left <= real_age[l]) and (real_age[h] <= right) then
      begin
        if (l = h) and (it[k] >= count) then
          begin
            res := real_age[l];
            count := 0;
            exit;
          end;

        if it[k] < count then
          begin
            count := count - it[k];
            exit;
          end;

        get(k*2,l,mid);
        get(k*2+1,mid+1,h);
        exit;
      end;

    mid := (l+h) div 2;
    get(k*2,l,mid);
    get(k*2+1,mid+1,h);
  end;

procedure solve;
  var
    i:longint;
  begin
    for i:=1 to nque do
      case que[i].ch of
        '+':
          begin
            update(1,1,nage,que[i].x,1);
          end;
        '-':
          begin
            update(1,1,nage,que[i].x,-1);
          end;
        '?':
          begin
            count := que[i].x;
            left := que[i].y;
            right := que[i].z;
            res := 0;

            get(1,1,nage);

            writeln(fo,res);
          end;
        end;
  end;

begin
  assign(Fi,fin);reset(fi);
  assign(fo,fout);rewrite(Fo);

  enter;
  init;
  make_age;
  roirac_age;
  solve;

  close(Fo);close(Fi);
end.

Download