P1486 [NOI2004] 郁闷的出纳员

整体思路，分块+2分+优先队列

s是块长，kuai记录每个块的整体信息，优先队列，存负的，因此是小根堆，维护要离职的员工，d记录整体增减量

#include<bits/stdc++.h>
using namespace std;
const int s=448,p=100000;
int read(){
	int x=0;
	bool flag=false;
	char ch=getchar();
	while(ch>57||ch<48){
		if(ch=='-'){
			flag=true;
		}
		ch=getchar();
	}
	while(ch>=48&&ch<=57){
		x=(x<<1)+(x<<3)+(ch-48);
		ch=getchar();
	}
	return flag?-x:x;
}
int n,m,kuai[450],a[400003],d,minn,maxx,cnt;
//map<int,int>kuai,a;
priority_queue<int>q;
int up(int x,int y){
	return x%y?x/y+1:x/y;
}
void build(int x){
	n+=1;
	q.push(d-x);
	int k=up(x-d,s);
	kuai[k]+=1;
	a[x-d]+=1;
	maxx=max(maxx,x-d);
	return;
}
int grank(int x){
	int k=x/s,res=0;
	for(int i=1;i<=k;i++){
		res+=kuai[i];
	}
	for(int i=k*s+1;i<=x;i++){
		res+=a[i];
	}
	return res;
}
int query(int x){
	x=n-x+1;
	int l=minn,r=maxx,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(grank(mid)<x){
			l=mid+1;
		}else{
			r=mid;
		}
	}
	return l+d;
}
int main(){
	m=read(),minn=read()+p;
	int x;
	char op;
	while(m--){
		cin>>op;
		x=read();
		if(op=='I'){
			x+=p;
			if(x<minn){
				continue;
			}
			build(x);
		}else if(op=='A'){
			d+=x;
		}else if(op=='S'){
			d-=x;
			while((!q.empty())&&d-q.top()<minn){
				int k=up(-q.top(),s);
				a[-q.top()]-=1;
				kuai[k]-=1;
				q.pop();
				n-=1;
				cnt+=1;
			}
		}else{
			if(x>n){
				cout<<"-1\n";
				continue;
			}
			cout<<query(x)-p<<"\n";
		}
//		cout<<d<<"\n";
	} 
	cout<<cnt<<"\n";
	return 0;
}