FOCUS - Chuyên gia ruồi
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program FOCUS;
const
input = '';
output = '';
maxn = 200010;
var
q,pos: array[1..3 * maxn] of integer;
a,b,t: array[1..2 * maxn] of integer;
ch: array[1..maxn] of char;
n,num: integer;
fi,fo: text;
procedure add(i: integer);
begin
read(fi, q[i]);
inc(num);
a[num] := q[i];
pos[num] := i;
end;
procedure init;
var
i: integer;
begin
assign(fi, input);
reset(fi);
readln(fi, n);
num := 0;
for i := 1 to n do
begin
read(fi, ch[i]);
if ch[i] = '?' then
begin
read(fi, q[3 * i]);
add(3 * i + 1);
add(3 * i + 2);
end
else add(3 * i);
readln(fi);
end;
close(fi);
end;
procedure swap(var x,y: integer);
var
tmp: integer;
begin
tmp := x; x := y; y := tmp;
end;
procedure swapint(i,j: integer);
begin
swap(a[i],a[j]);
swap(pos[i],pos[j]);
end;
procedure quicksort;
procedure partition(l,h: integer);
var
i,j,p: integer;
begin
if l >= h then exit;
i := l; j := h; p := a[random(h - l + 1) + l];
repeat
while a[i] < p do inc(i);
while a[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;
partition(l,j);
partition(i,h);
end;
var
i,c: integer;
begin
partition(1,num);
c := 1;
q[pos[1]] := 1;
b[1] := a[1];
for i := 2 to num do
begin
if a[i] > a[i - 1] then inc(c);
q[pos[i]] := c;
b[c] := a[i];
end;
end;
procedure update(x,k: integer);
begin
while x <= 2 * 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;
procedure solve;
var
i,inf,sup,mid,tmp,tm,res: integer;
begin
assign(fo, output);
rewrite(fo);
for i := 1 to n do
if ch[i] = '+' then update(q[3 * i],1)
else if ch[i] = '-' then update(q[3 * i],-1)
else
begin
inf := q[3 * i + 1];
sup := q[3 * i + 2];
if calc(sup) - calc(inf - 1) < q[3 * i] then writeln(fo, 0) else
begin
tmp := calc(inf - 1);
repeat
mid := (inf + sup) div 2;
tm := calc(mid);
if tm < q[3 * i] + tmp then inf := mid + 1 else
begin
res := mid;
sup := mid - 1;
end;
until inf > sup;
writeln(fo, b[res]);
end;
end;
close(fo);
end;
begin
init;
quicksort;
solve;
end.