# 某岛

… : "…アッカリ～ン . .. . " .. .
September 27, 2014

## BZOJ 1503. 郁闷的出纳员

http://www.lydsy.com/JudgeOnline/problem.php?id=1503

### Analysis:

//}/* .................................................................................................................................. */

namespace SBT{
const int NN = int(1e5) + 9;
int c[2][NN], sz[NN], ky[NN], tot;
#define lx l[x]
#define rx r[x]
#define l c[d]
#define r c[!d]
#define kx ky[x]
#define sx sz[x]
#define d 0
int new_node(int v = 0){
int x=++tot;lx=rx=0;
sx=1;kx=v;
return x;
}

void upd(int x){
sx=sz[lx]+1+sz[rx];
}
#undef d
void rot(int &x,int d){
int y=rx;rx=l[y];l[y]=x;
upd(x),upd(y),x=y;
}

void fix(int &x,int d){
if (sz[l[lx]] > sz[rx]) rot(x,!d);
else{
if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
else return;
}
d=0,fix(lx,0),fix(rx,1);
fix(x,0),fix(x,1);
}
#define d 0

int mini(int x){
if (lx) return mini(lx);
return ky[x];
}

void iod(int x){
if (!x) return;
iod(lx); printf("%d ", ky[x]); iod(rx);
}

void Ins(int &x,int v){
if(!x) x = new_node(v);
else{
++sz[x]; Ins(c[v>kx][x],v);
fix(x,v>=kx);
}
}

int d_key; void Del(int &x,int v){
--sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
if(!lx||!rx) d_key = kx, x = lx | rx;
else Del(lx,v+1), kx = d_key;
}
else Del(c[v>kx][x],v);
}

int Rank(int x,int v){
int z=0;while(x){
if(kx<v){
z+=sz[lx]+1;
x=rx;
}
else x=lx;
}
return z;
}

int Select(int x,int k){
if (sz[lx] == k) return ky[x];
return sz[lx]>k?Select(lx,k):Select(rx,k-sz[lx]-1);
}

bool Find(int x,int v){
if (!x) return 0;if (kx==v) return 1;
return Find(c[v>kx][x],v);
}

void Init(){
tot = 0;
}

#undef d
#undef l
#undef r
#undef lx
#undef rx
#undef sx
#undef kx
} using namespace SBT;

int n, b, d, rt, cnt;

void Insert(int v){
if (v < b) return;
v -= d; Ins(rt, v);
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
while (~scanf("%d %d", &n, &b)){

Init(); rt = cnt = 0;

DO(n){
char cmd; RC(cmd); int k; RD(k); switch(cmd){
case 'I':
Insert(k);
break;
case 'A':
d += k;
break;
case 'S':
d -= k;
while (rt && mini(rt) + d < b) Del(rt, mini(rt)),++cnt;
break;
default:
if (k > sz[rt]) puts("-1");
else{
OT(Select(rt,sz[rt]-k)+d);
}
}
}

OT(cnt);
}
}