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.