题解：P1486 [NOI2004] 郁闷的出纳员

/*

*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[3000005], rang = 3000005;
void add(int x, int y){
	for(int i = x; i <= rang; i += i & -i){
		c[i] += y;
	}
}
int get(int x){
	int anst = 0;
	for(int i = x; i > 0; i -= i & -i){
		anst += c[i];
	} 
	return anst;
}
int kth(int k){
	int sum = 0, x = 0;
	//currently have a total of sum that are <= x
	for(int i = 35; i >= 0; i--){
		int powi = (1LL << i);
		if(x + powi <= rang && sum + c[x + powi] < k){
			//within range and within kth
			//we can just use c[x + powi] instead of using get
			//because we know all previous adding to x
			//all are 2 to the jth power where j > i, so powi
			//itself must be the lowbit of x + powi
			x += powi;
			sum += c[x];
		}
	}
	return x + 1;
}
int n, mi, tot, leav, num, INF = 5e5;
signed main(){
	cin>>n>>mi;
	mi += INF;
	while(n--){
		char typ;
		int x;
		cin>>typ>>x;
		if(typ == 'I'){
			if(x - tot + INF < mi){
				continue;
				//KEY BUG!!!
			}
			add(x - tot + INF, 1);
			num++;
		}
		if(typ == 'A'){
			mi -= x;
			tot += x;
		}
		if(typ == 'S'){
			mi += x;
			tot -= x;
			int curmi = kth(1);//smallest
			while(curmi < mi){
				//each will only be erased once we'll be fine
				add(curmi, -1);
				leav++;
				num--;
				//leave
				curmi = kth(1);
			}
		}
		if(typ == 'F'){
			if(x > num)cout<<-1<<endl;
			else cout<<kth(num - x + 1) + tot - INF<<endl;
		}
	}
	cout<<leav<<endl;
	return 0;
}