[NOI2004]郁闷的出纳员

题目：BZOJ1503、洛谷P1486、codevs1286、Vijos P1507。

题目大意：叫你编一个工资统计程序，具体操作见题目。

解题思路：建一棵权值线段树，保存每种工资的数量，由于工资可能有负，可以先对每个工资加上200000，然后进行处理。对于加减工资操作，直接用个变量储存工资变化即可。减工资时相当于区间赋0操作。查询时先把他转化为求第k小，再查询即可。

C++ Code：

#include<cstdio>
#include<cstring>
using namespace std;
int m,down,bh,k,ans;
const int n=404000;
int d[4005050];
char s[3];
void add(int l,int r,int o,int p){
	if(l!=r)
	if(d[o]==0)d[o<<1]=d[o<<1|1]=0;
	++d[o];
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)add(l,mid,o<<1,p);else
	add(mid+1,r,o<<1|1,p);
}
void del(int l,int r,int o,int p){
	if(d[o]==0)d[o<<1]=d[o<<1|1]=0;
	if(r<=p){
		ans+=d[o];
		d[o]=0;
		return;
	}
	int mid=l+r>>1;
	del(l,mid,o<<1,p);
	if(mid<p)del(mid+1,r,o<<1|1,p);
	d[o]=d[o<<1]+d[o<<1|1];
}
int query(int l,int r,int o,int k){
	if(d[o]==0)d[o<<1]=d[o<<1|1]=0;
	if(l==r)return l;
	int mid=l+r>>1;
	if(d[o<<1]>=k)return query(l,mid,o<<1,k);
	else return query(mid+1,r,o<<1|1,k-d[o<<1]);
}
int main(){
	scanf("%d%d",&m,&down);
	down+=200000;
	memset(d,0,sizeof d);
	bh=0;
	ans=0;
	while(m--){
		scanf("%s%d",s,&k);
		switch(s[0]){
			case'I':
				k+=200000;
				if(k>=down)add(1,n,1,k-bh);
				break;
			case'A':
				bh+=k;
				break;
			case'S':
				bh-=k;
				del(1,n,1,down-bh-1);
				break;
			case'F':
				k=d[1]-k+1;
				if(k<1)puts("-1");else
				printf("%d
",query(1,n,1,k)+bh-200000);
		}
	}
	printf("%d
",ans);
	return 0;
}