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\n");

			else printf("%d\n", get_val(root, size[root] - x) + lazy);

			}

		}

	printf("%d\n", c);

	return 0;

	}