P1486 [NOI2004]郁闷的出纳员

题目描述
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

输入输出格式
输入格式：
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。

接下来的n行，每行表示一条命令。命令可以是以下四种之一：

名称格式作用

I命令 I_k 新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。

A命令 A_k 把每位员工的工资加上k

S命令 S_k 把每位员工的工资扣除k

F命令 F_k 查询第k多的工资

_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。

在初始时，可以认为公司里一个员工也没有。

输出格式：
输出文件的行数为F命令的条数加一。

对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。

输出文件的最后一行包含一个整数，为离开公司的员工的总数。

降低或提高工资时，把 (Treap) 树中全部节点拿出，修改后再放回，在时间上不太能够接受（虽然这题数据是可以的），我们用一个变量 (lazy) 维护从刚开始一共变化了多少工资，所以几个操作转化为如下操作：

1.来新人：由于有一个基础变化 (lazy) 新人享受不到，一个人只能享受加入公司之后的工资变化，所以我们向 (Treap) 中加入 (x - lazy)

2.加工资：并不会影响员工的走留，直接累计到 (lazy) 即可

3.减工资：先更新 (lazy) 。因为所有员工的最低工资是一样的，所以要走总是工资最少的。我们不断查询工资最少的员工，看是否留下，若是不留则删除继续看下一个工资多一点的走不走。一旦发现有一个不走了，那么后面的都是工资更多的，也就不会走了。

4.查询第k小：注意是第k小。直接查询即可，查出来加上 (lazy) 即为答案

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int RD(){
	int flag = 1, out = 0;char c = getchar();
	while(c < '0' || c > '9'){if(c == '-')flag = -1;c = getchar();}
	while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
	return flag * out;
	}
const int maxn = 1000019, INF = 1e9 + 19;
int ch[maxn][2];
int size[maxn], cnt[maxn];
int val[maxn], dat[maxn];
int root, tot;
int New(int v){
	val[++tot] = v;dat[tot] = rand();
	size[tot] = cnt[tot] = 1;
	return tot;
	}
void pushup(int id){size[id] = size[ch[id][0]] + size[ch[id][1]] + cnt[id];}
void build(){
	root = New(-INF);
	ch[root][1] = New(INF);
	pushup(root);
	}
void Rotate(int &id, int d){
	int temp = ch[id][d ^ 1];
	ch[id][d ^ 1] = ch[temp][d];
	ch[temp][d] = id;
	id = temp;
	pushup(ch[id][d]), pushup(id);
	}
void insert(int &id, int v){
	if(!id){id = New(v);return ;}
	if(val[id] == v){cnt[id]++;pushup(id);return ;}
	int d = v < val[id] ? 0 : 1;
	insert(ch[id][d], v);
	if(dat[ch[id][d]] > dat[id])Rotate(id, d ^ 1);
	pushup(id);
	}
void Remove(int &id, int v){
	if(!id)return ;
	if(val[id] == v){
		if(cnt[id] > 1){cnt[id]--;pushup(id);return ;}
		if(ch[id][0] || ch[id][1]){
			if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]]){
				Rotate(id, 1);
				Remove(ch[id][1], v);
				}
			else Rotate(id, 0), Remove(ch[id][0], v);
			pushup(id);
			}
		else id = 0;
		return ;
		}
	v < val[id] ? Remove(ch[id][0], v) : Remove(ch[id][1], v);
	pushup(id);
	}
int get_val(int id, int rank){
	if(!id)return INF;
	if(size[ch[id][0]] >= rank)return get_val(ch[id][0], rank);
	else if(size[ch[id][0]] + cnt[id] >= rank)return val[id];
	else return get_val(ch[id][1], rank - size[ch[id][0]] - cnt[id]);
	}
int na, minn;
int lazy, c, sum;
int main(){
	na = RD();minn = RD();
	build();
	char cmd;int x;
	for(int i = 1;i <= na;i++){
		cin>>cmd;
		if(cmd == 'I'){
			x = RD();
			if(x >= minn){
				insert(root, x - lazy);
				sum++;
				}
			}
		else if(cmd == 'A'){
			lazy += RD();
			}
		else if(cmd == 'S'){
			x = RD();
			lazy -= x;
			if(sum == 0)continue;
			bool flag = 1;
			while(flag){
				int MIN = get_val(root, 2);
				if(MIN + lazy < minn)Remove(root, MIN), c++, sum--;
				else flag = 0;
				if(sum == 0)break;
				}
			}
		else if(cmd == 'F'){
			x = RD();
			if(sum < x)printf("-1
");
			else printf("%d
", get_val(root, size[root] - x) + lazy);
			}
		}
	printf("%d
", c);
	return 0;
	}