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.