郁闷的出纳员
题目: http://www.zybbs.org/JudgeOnline/problem.php?id=1503
题目大意：见题目吧，
题意很明确，
就是补充一点，相同的工资是不能合并的，比如说
有11，
11，
11，那么第一是11，
第三也是11
思路：也没什么思路，
就是为了测试splayTree模板，可能有点儿技巧的就是两个地方，一是在全体增加和全体减少的时候，用一个东西del存下来，将数字x放入树时，放入x-del
这样对于每次的增加操作就不用遍历树了，只需在减少的时候进行删除操作。原理也很简单。
第二是在删除的时候，如果一个节点rt不满足了，直接将其及左树，将右树接到rt父节点处。
提交情况：CE。。。-——》wa——》
TLE—》WA
——》AC
AC
code：
#include
<cstdio>
#include
<cstring>
#define
maxn 1000000
struct
splayTreeNode{
int key, size, id;
splayTreeNode* son[2],* father;
void init(int k, int sz, int chi, splayTreeNode* l, splayTreeNode*
r, splayTreeNode* fa){
key = k, size = sz, id = chi, son[0] = l, son[1] = r, father =
fa;
}
};
struct
splayTree{
splayTreeNode* nul, *link;
#define root nul->son[0]
int ad;
splayTree(){
link = new splayTreeNode[maxn];
ad = 0;
nul = &(link[ad ++]);
nul->init(0, 0, 0, NULL, NULL, NULL);
}
void rotate(splayTreeNode* &rt, int son1, int
son2){
splayTreeNode* temp = rt->son[son1];
rt->son[son1] =
temp->son[son2];
rt->size -= temp->size;
if(temp->son[son2] != NULL){
temp->size -=
temp->son[son2]->size;
rt->size +=
temp->son[son2]->size;
temp->son[son2]->father =
rt;
temp->son[son2]->id =
son1;
}
temp->son[son2] = rt;
temp->father = rt->father;
temp->id = rt->id;
temp->size += rt->size;
rt->father = temp;
rt->id = son2;
rt = temp;
}
void splay(splayTreeNode* x, splayTreeNode* rt){
if(x->father == rt) return;
splayTreeNode* y = x->father,* z =
x->father->father;
if(z == rt){
if(y->son[0] == x)
rotate(z->son[y->id], 0,
1);
else rotate(z->son[y->id], 1,
0);
}
else{
if(y->id == x->id){
rotate(z->father->son[z->id],
x->id, (x->id)^1);
rotate(y->father->son[y->id],
x->id, (x->id)^1);
}
else{
rotate(y->father->son[y->id],
x->id, (x->id)^1);
rotate(z->father->son[z->id],
y->id, (y->id)^1);
}
}
splay(x, rt);
}
void insert(int x, int chi, splayTreeNode* &rt,
splayTreeNode* rf){
if(rt == NULL){
rt = &link[ad ++];
if(rf == nul) nul->son[0] = root;
rt->init(x, 1, chi, NULL, NULL, rf);
splay(rt, this->nul);
return;
}
rt->size ++;
if(x < rt->key)
insert(x, 0, rt->son[0], rt);
else insert(x, 1, rt->son[1], rt);
}
void rise(int x, splayTreeNode* rt){
if(rt == NULL) return;
rt->key += x;
rise(x, rt->son[0]);
rise(x, rt->son[1]);
}
void reduce(int x, int min, splayTreeNode* rt){
if(rt == NULL) return;
if(rt->key + x < min){
rt->father->son[rt->id]
= rt->son[1];
if(rt->son[1] != NULL){
rt->son[1]->id =
rt->id;
rt->son[1]->father =
rt->father;
reduce(x, min, rt->son[1]);
}
}
else{
reduce(x, min, rt->son[0]);
rt->size = 1;
if(rt->son[1] != NULL) rt->size +=
rt->son[1]->size;
if(rt->son[0] != NULL) rt->size +=
rt->son[0]->size;
}
}
int find(int k, splayTreeNode* rt){
if(rt == NULL || rt->size < k) return
-1;
if(rt->son[1] != NULL){
if(rt->son[1]->size == k - 1) return
rt->key;
if(rt->son[1]->size >=
k) return find(k, rt->son[1]);
return find(k - (rt->son[1]->size +
1), rt->son[0]);
}
else{
if(k == 1) return rt->key;
else return find(k - 1, rt->son[0]);
}
}
};
int
main(){
char ord[3];
int k, n, min, tot, del;
while(~scanf("%d %d", &n,
&min)){
splayTree spl;
del = tot = 0;
for(int i = 0; i < n; ++ i){
scanf("%1s %d", ord, &k);
switch(ord[0]){
case 'I':
>= min){
tot ++;
spl.insert(k - del, 0, spl.root, spl.nul);
}
break;
case 'A':
+= k;
break;
case 'S':
del -= k;
spl.reduce(del, min, spl.root);
break;
case 'F':
int ans = spl.find(k, spl.root);
printf("%d\n", ans == -1 ? ans : (ans + del));
break;
}
}
printf("%d\n", tot - spl.root->size);
}
return 0;
}