#include <stdio.h>
#include <math.h>
#include <string.h>
#define maxn 100005
#define nil 0
#define oo 1000000000
int n, minp, root, tot, w;
int d[maxn], son[maxn][2], fa[maxn], s[maxn];
inline void update(int rot)
{
s[rot] = s[son[rot][0]] + s[son[rot][1]] + 1;
}
void rotate(int x, int w)
{
int y = fa[x];
son[y][w ^ 1] = son[x][w];
if(son[x][w] != nil) fa[son[x][w]] = y;
fa[x] = fa[y];
if(fa[y] != nil)
{
if(y == son[fa[y]][0]) son[fa[y]][0] = x;
else son[fa[y]][1] = x;
}
son[x][w] = y; fa[y] = x;
update(y); update(x);
}
void splay(int x, int poi)
{
if(x == nil) return;
while(fa[x] != poi)
{
if(fa[fa[x]] == poi)
{
if(x == son[fa[x]][0]) rotate(x, 1);
else rotate(x, 0);
}
else
{
if(fa[x] == son[fa[fa[x]]][0])
{
if(x == son[fa[x]][0])
{
rotate(fa[x], 1); rotate(x, 1);
}
else
{
rotate(x, 0); rotate(x, 1);
}
}
else
{
if(x == son[fa[x]][0])
{
rotate(x, 1); rotate(x, 0);
}
else
{
rotate(fa[x], 0); rotate(x, 0);
}
}
}
}
if(poi == nil) root = x;
}
void insert(int rot, int x)
{
++s[rot];
if(d[rot] <= x)
{
if(son[rot][1] == nil)
{
d[++tot] = x;
s[tot] = 1;
fa[tot] = rot;
son[rot][1] = tot;
son[tot][0] = son[tot][1] = nil;
splay(rot, nil);
}
else
{
insert(son[rot][1], x);
}
}
else
{
if(son[rot][0] == nil)
{
d[++tot] = x;
s[tot] = 1;
fa[tot] = rot;
son[rot][0] = tot;
son[tot][0] = son[tot][1] = nil;
splay(rot, nil);
}
else
{
insert(son[rot][0], x);
}
}
}
int succ(int rot, int k)
{
if(rot == nil) return nil;
if(d[rot] >= k)
{
int t = succ(son[rot][0], k);
if(t == nil) return rot;
else return t;
}
else
{
return succ(son[rot][1], k);
}
}
int select(int rot, int k)
{
if(rot == nil || k < 0) return -1;
if(s[son[rot][1]] + 1 == k) return d[rot] + w;
if(s[son[rot][1]] >= k) return select(son[rot][1], k);
return select(son[rot][0], k - s[son[rot][1]] - 1);
}
int main()
{
char opt;
int k, sum = 0;
printf("请输入下面命令条数和工资下界：");
scanf("%d%d", &n, &minp);
d[root = ++tot] = (oo << 1);
s[tot] = 1;
fa[tot] = son[tot][0] = son[tot][1] = nil;
while(n--)
{
printf("请输入命令：");
scanf("\n%c %d", &opt, &k);
switch(opt)
{
case 'I': if(k >= minp)
{
insert(root, k - w);
++sum;
}
break;
case 'A': w += k;
break;
case 'S': w -= k;
splay(succ(root, minp - w), nil);
s[root] -= s[son[root][0]];
son[root][0] = nil;
break;
case 'F': printf("当前工资第%d的员工所拿的工资数：%d\n", k,select(root, k + 1));
break;
default : break;
}
}
printf("命令结束。\n离开公司的员工的总数：%d\n", sum - s[root] + 1);
printf("\n请输入任意键退出");
getch();
return 0;
}
