郁闷的出纳员
问题描述
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。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
样例输入
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
样例输出
10
20
-1
2
约定
- I命令的条数不超过100000
- A命令和S命令的总条数不超过100
- F命令的条数不超过100000
- 每次工资调整的调整量不超过1000
- 新员工的工资不超过100000
题意
要求设计一种数据结构，能够快速进行以上4种操作，完成对整个工资单的动态维护。
分析
这种动态问题，很明显的要用到动态的数据结构来维护，可以使用一般的线段树或者平衡树进行解决，而本题的特点非常适合Splay的发挥。
首先是看到A和S命令，都是针对整个工资单中的所有员工进行操作的，因此可以考虑不改变每个员工单独的值（n个员工就要改n次，开玩笑……），而是用另外一个独立的变量把所有的加减操作都记录下来，判断员工出局的时候再结合题目给定的最低值计算出下限。这里要注意的是，但是当一个员工新加入时，之前的调工资操作应该对他是不产生影响的，因为那时候这个人还不在，但是用来记录工资加减的独立变量只有一个，所以在新员工加入的时候要把之前的工资加减情况减掉，这样最后计算时才可以把前面的部分抵消掉。
另，若一个人的初始工资小于底线，则这个人的离开不算到最后的答案中。
插入和找第k值都是基本的二叉树很容易解决，删除操作是本题的重点：
测试模板和修改删除部分花了大把的时间..T_T
根据上面的思路，用mi表示给定的底线，tot记录工资加减情况，则最后mi-tot就是初始工资的相对底线，每次出现S，也就是减了工资之后，就需要把树中低于mi-tot的所有值都删掉。但是splay在实际使用过程中，若树中存在多个mi-tot的值，则由于中间有各种旋转、splay操作，直接查找mi-tot得到的位置不能够确定剩下的是在左子树还是右子树还是两个都有。于是采取的方案：
1.搜索mi-tot-1
2.若不存在，则插入一个mi-tot-1，将其旋转到根，然后把根和左子树都删掉！！！树中剩下的就是大于mi-tot-1，也就是大于等于mi-tot的值了，注意计数时不要忘记这个根是自己加进去的，不要算进去。
3.若存在mi-tot-1，则同样将根和左子树都删掉，然后在右子树中搜索mi-tot-1，旋转到根删掉，不断重复直到整棵树中不存在mi-tot-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100010
int sons[MAXN][2];
int father[MAXN],size[MAXN],data[MAXN];
int spt=0,spttail=0,tot=0,men=0;
void rotate(int x,int w)
{
int y=father[x];
sons[y][1-w]=sons[x][w];
if (sons[x][w]) father[sons[x][w]]=y;
father[x]=father[y];
if (father[y])
if (y==sons[father[y]][0]) sons[father[y]][0]=x;
else sons[father[y]][1]=x;
sons[x][w]=y;
father[y]=x;
size[x]=size[y];
size[y]=size[sons[y][0]]+size[sons[y][1]]+1;
}
void splay(int x,int y)
{
if (!x) return ;
while(father[x]!=y)
{
if (father[father[x]]==y)
if (x==sons[father[x]][0]) rotate(x,1);
else rotate(x,0);
else
if (father[x]==sons[father[father[x]]][0])
if (x==sons[father[x]][0])
{
rotate(father[x],1);
rotate(x,1);
} else
{
rotate(x,0);
rotate(x,1);
}
else
if (x==sons[father[x]][1])
{
rotate(father[x],0);
rotate(x,0);
} else
{
rotate(x,1);
rotate(x,0);
}
}
if (!y) spt=x;
}
void search(int x,int w)
{
while(data[x]!=w)
{
if (w<data[x])
{
if (sons[x][0]) x=sons[x][0];
else break;
} else if (w>data[x])
{
if (sons[x][1]) x=sons[x][1];
else break;
}
}
splay(x,0);
}
void insert(int w)
{
spttail++;
data[spttail]=w;
size[spttail]=1;
sons[spttail][0]=0;
sons[spttail][1]=0;
if (!spt)
{
father[spttail]=0;
spt=spttail;
} else
{
int x=spt;
while(1)
{
size[x]++;
if (w<data[x])
if (sons[x][0]) x=sons[x][0];
else break;
else
if (sons[x][1]) x=sons[x][1];
else break;
}
father[spttail]=x;
if (w<data[x]) sons[x][0]=spttail;
else sons[x][1]=spttail;
splay(spttail,0);
}
}
void select(int x,int v)
{
while(v!=size[sons[x][0]]+1)
{
if (v<=size[sons[x][0]]) x=sons[x][0];
else
{
v-=size[sons[x][0]]+1;
x=sons[x][1];
}
}
splay(x,0);
}
int main()
{
freopen("cashier.in","r",stdin);
freopen("cashier.out","w",stdout);
int n,mi;
scanf("%d%d",&n,&mi);
spt=0;
spttail=0;
tot=0;
men=0;
for (int i=1;i<=n;i++)
{
char c;
c=getchar();
while(c!='I'&&c!='A'&&c!='S'&&c!='F') c=getchar();
int k;
scanf("%d",&k);
if (c=='I')
{
if (k>=mi) insert(k-tot);
} else
if (c=='A')
{
tot+=k;
} else
if (c=='S')
{
tot-=k;
search(spt,mi-tot-1);
if (data[spt]!=mi-tot-1)
{
insert(mi-tot-1);
men+=size[sons[spt][0]];
spt=sons[spt][1];
father[spt]=0;
} else
{
men+=size[sons[spt][0]]+1;
spt=sons[spt][1];
father[spt]=0;
search(spt,mi-tot-1);
while(data[spt]==mi-tot-1)
{
men++;
spt=sons[spt][1];
father[spt]=0;
search(spt,mi-tot-1);
}
}
} else
{
if (k>size[spt]) printf("-1\n");
else
{
select(spt,size[spt]-k+1);
printf("%d\n",data[spt]+tot);
}
}
}
printf("%d\n",men);
return 0;
}
|