TYPE

bst = RECORD

pr, lc, rc, val, vw, sz, mn: LONGINT;

END;

VAR

root, min, res, res2, u1, p, newnode: LONGINT;

tr: ARRAY[1..100000] OF bst;

ud: ARRAY[1..100000] OF LONGINT;

f0: BOOLEAN;

PROCEDURE turn_left(i: LONGINT);

VAR

j, k, az, bz, cz: LONGINT;

BEGIN

j := tr[i].rc; k := tr[i].pr;

IF tr[i].lc = 0 THEN az := 0 ELSE az := tr[tr[i].lc].sz;

IF tr[j].lc = 0 THEN bz := 0 ELSE bz := tr[tr[j].lc].sz;

IF tr[j].rc = 0 THEN cz := 0 ELSE cz := tr[tr[j].rc].sz;

IF (k 0) AND (tr[k].lc = i) THEN tr[k].lc := j;

IF (k 0) AND (tr[k].rc = i) THEN tr[k].rc := j;

tr[i].pr := j; tr[j].pr := k; tr[i].rc := tr[j].lc;

IF tr[j].lc 0 THEN tr[tr[j].lc].pr := i;

tr[j].lc := i;

tr[i].sz := az + bz + tr[i].mn; tr[j].sz := tr[i].sz + cz + tr[j].mn;

END;

PROCEDURE turn_right(i: LONGINT);

VAR

j, k, az, bz, cz: LONGINT;

BEGIN

j := tr[i].lc; k := tr[i].pr;

IF tr[i].rc = 0 THEN az := 0 ELSE az := tr[tr[i].rc].sz;

IF tr[j].lc = 0 THEN bz := 0 ELSE bz := tr[tr[j].lc].sz;

IF tr[j].rc = 0 THEN cz := 0 ELSE cz := tr[tr[j].rc].sz;

IF (k 0) AND (tr[k].lc = i) THEN tr[k].lc := j;

IF (k 0) AND (tr[k].rc = i) THEN tr[k].rc := j;

tr[i].pr := j; tr[j].pr := k; tr[i].lc := tr[j].rc;

IF tr[j].rc 0 THEN tr[tr[j].rc].pr := i;

tr[j].rc := i;

tr[i].sz := az + bz + tr[i].mn; tr[j].sz := tr[i].sz + cz + tr[j].mn;

END;

PROCEDURE ins_root;

BEGIN

root := newnode;

p := 1;

END;

PROCEDURE del_root;

BEGIN

root := 0;

p := 0;

END;

PROCEDURE ins1(x: LONGINT);

VAR

i, j, k: LONGINT;

BEGIN

INC(p);

i := root; u1 := 0;

WHILE i 0 DO BEGIN

k := i;

IF tr[i].val = x THEN BEGIN

INC(tr[i].mn); INC(tr[i].sz); f0 := TRUE;

FOR j:=1 TO u1 DO INC(tr[ud[j]].sz);

EXIT;

END;

INC(u1);

ud[u1] := i;

IF tr[i].val > x THEN i := tr[i].lc ELSE i := tr[i].rc;

END;

tr[newnode].pr := k; f0 := FALSE;

IF tr[k].val > x THEN tr[k].lc := newnode ELSE tr[k].rc := newnode;

FOR j:=1 TO u1 DO INC(tr[ud[j]].sz);

END;

PROCEDURE ins2;

VAR

i, j: LONGINT;

BEGIN

FOR i:=u1 DOWNTO 1 DO BEGIN

j := ud[i];

IF tr[j].vw >= tr[newnode].vw THEN EXIT;

IF tr[j].rc = newnode THEN turn_left(j) ELSE turn_right(j);

END;

root := newnode;

END;

PROCEDURE del1(i: LONGINT);

VAR

j, w1, w2: LONGINT;

BEGIN

DEC(p); INC(res2);

IF tr[i].mn > 1 THEN BEGIN

DEC(tr[i].mn);

j := tr[i].pr;

WHILE j 0 DO BEGIN DEC(tr[j].sz); j := tr[j].pr; END;

EXIT;

END;

REPEAT

IF tr[i].lc = 0 THEN w1 := 0 ELSE w1 := tr[tr[i].lc].vw;

IF tr[i].rc = 0 THEN w2 := 0 ELSE w2 := tr[tr[i].rc].vw;

IF (w1 = 0) AND (w2 = 0) THEN BEGIN

IF i = tr[tr[i].pr].lc THEN tr[tr[i].pr].lc := 0 ELSE tr[tr[i].pr].rc := 0;

j := tr[i].pr;

WHILE j 0 DO BEGIN DEC(tr[j].sz); j := tr[j].pr; END;

EXIT;

END;

IF w1 > w2 THEN turn_right(i) ELSE turn_left(i);

UNTIL FALSE;

END;

PROCEDURE del2;

VAR

i: LONGINT;

BEGIN

i := root;

WHILE tr[i].lc 0 DO i := tr[i].lc;

IF tr[i].val >= min THEN BEGIN f0 := FALSE; EXIT; END;

IF p = 1 THEN del_root ELSE del1(i);

END;

PROCEDURE add(i, x: LONGINT);

BEGIN

IF i = 0 THEN EXIT;

INC(tr[i].val, x);

add(tr[i].lc, x); add(tr[i].rc, x);

END;

FUNCTION find(i, x: LONGINT): LONGINT;

VAR

s0: LONGINT;

BEGIN

IF tr[i].lc = 0 THEN s0 := 0 ELSE s0 := tr[tr[i].lc].sz;

IF x s0 + tr[i].mn THEN EXIT(find(tr[i].rc, x - s0 - tr[i].mn));

EXIT(tr[i].val);

END;

PROCEDURE xxx;

VAR

c, c2: CHAR;

n, i, k: LONGINT;

BEGIN

READLN(n, min);

p := 0; root := 0; newnode := 0; RANDOMIZE;

FOR i:=1 TO n DO BEGIN

READLN(c, c2, k);

IF c = 'I' THEN BEGIN

IF k < min THEN CONTINUE;

INC(newnode);

tr[newnode].pr := 0; tr[newnode].lc := 0; tr[newnode].rc := 0;

tr[newnode].val := k; tr[newnode].vw := RANDOM(99999999) + 1;

tr[newnode].sz := 1; tr[newnode].mn := 1;

IF p = 0 THEN BEGIN ins_root; CONTINUE; END;

ins1(k);

IF NOT f0 THEN ins2;

END;

IF c = 'A' THEN add(root, k);

IF (c = 'S') AND (p > 0) THEN BEGIN

add(root, -k);

f0 := TRUE; WHILE f0 AND (p > 0) DO del2;

END;

IF c = 'F' THEN BEGIN

IF k > p THEN WRITELN(-1) ELSE WRITELN(find(root, p - k + 1));

END;

END;

WRITELN(res2);

END;

BEGIN

xxx;

END.

就过一个点，其它全栈溢出。