zkw值域线段树

#include <iostream>
using namespace std;
const int N = 4e5, len = 2e5;
int n, Min;
int st[(N+10)<<2], tn;
inline void update(int x, int v) { for(x+=tn;x;x>>=1) st[x] += v; }
inline int query(int l, int r) {
	int ret = 0;
	for(l+=tn-1,r+=tn+1;l^r^1;l>>=1,r>>=1) {
		if(~l&1) ret += st[l^1];
		if(r&1) ret += st[r^1];
	}
	return ret;
}
inline void clear(int l, int r) {
	for(l+=tn-1,r+=tn+1;l^r^1;l>>=1,r>>=1) 
		for(int i=l+1;i<r;++i) st[i] = 0;
}
#define mid ((l+r)>>1)
inline int kth(int l, int r, int k) {
	while(l<r) {
		int q = query(l, mid);
		if(q>=k) r=mid;
		else k-=q, l=mid+1;
	}
	if(query(l, l) < k) return r;
	return l;
}
int main() {
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	for(tn=1;tn+1<=N;tn<<=1);
	cin>>n>>Min;
	int low = Min, exp = 0, cnt = 0, tot = 0;
	Min += len;
	while(n--) {
		char t; int x;
		cin>>t>>x;
		if(t=='I'&&x>=low) update(x-exp+len, 1), ++tot;
		else if(t=='A') Min-=x, exp+=x;
		else if(t=='S') {
			Min+=x, exp-=x;
			if(Min>=1) {
				int q = query(0, Min-1);
				if(q > 0) {
					cnt += q, tot -= q;
					clear(0, Min-1);
				}
			}
		} else if(t=='F') {
			if(x > query(Min, N)) cout<<"-1\n";
			else cout<<kth(0, N, tot-x+1)+exp-len<<"\n";
		}
	}
	cout<<cnt;
	return 0;
}