郁闷的出纳员问题

解题思路

最开始一个员工都没有，我们要陆续找员工进来，一共有四个操作。

第一种操作是招入一个新员工，有一个初始工资，第二种操作是给所有员工涨薪，第三种操作时给所有员工减薪，第四个操作是查询第 $k$ 多的工资。

另外，如果某个员工的薪水低于某个定值，将被删去。

如果不看第二、三个操作，那么这就是一个动态加点，动态查询第 $k$ 大数的问题，可以用平衡树来维护一个 $cnt$，表示子树中的节点个数，就能动态求第 $k$ 大数。

然后加上第二、三个操作，可以发现我们还要进行区间修改，虽然平衡树是支持区间修改操作的，但是本题比较特殊，每次都将所有员工进行加薪减薪，也就是每次只对一个固定的区间进行修改。因此我们可以记录一个全局偏移量 $delta$，对于每个员工的工资，只要在原工资的基础上再加上 $delta$ 就是真实的工资。这样我们在二、三操作时我们只需要维护一下 $delta$ 即可。

对于某些员工低于基本工资需要删去，只要我们保证序列是有序的，那么每次一定会删除一个前缀，只需要用 Splay 的删除方法来删除即可，另外为了防止找前驱和后继时出现越界问题，所以可以安排两个哨兵来防止边界问题。

我们每次要删除的应该是所有真实工资小于最低工资的员工，那么这个区间的前驱就是左哨兵，后继应该是最小的一个真实工资大于等于最低工资的人，找最小的一个真实工资大于等于最低工资的员工，就是平衡树的一个一般操作，可以递归查找。找到区间的前驱和后继我们就可以很简单的执行删除操作。

以上就是全部操作的处理方式，是一个经典的 Splay 的应用。

注意：本题维护的是一个有序序列，Splay 既可以维护一个普通序列，也可以维护一个有序序列。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n, minv, delta; //命令数量、最低工资、偏移量

struct Node
{
    int s[2], p, v; //子节点的下标、父节点的下标、工资
    int cnt; //子树中的节点个数

    void init(int _v, int _p) //初始化
    {
        v = _v;
        p = _p;
        cnt = 1;
    }
}tr[N]; //Splay
int root, idx; //根节点的下标、指针

void pushup(int x) //通过两个子节点的信息得到当前节点的信息
{
    tr[x].cnt = tr[tr[x].s[0]].cnt + tr[tr[x].s[1]].cnt + 1;
}

void rotate(int x) //左旋、右旋
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;

    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k) //将 x 转到 k 的子节点
{
    while(tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k)
        {
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k) root = x;
}

int insert(int v) //将一个数值插入 Splay
{
    int u = root, p = 0;
    while(u) p = u, u = tr[u].s[v > tr[u].v];
    u = ++idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);
    splay(u, 0);
    return u;
}

int get(int v) //获取大于等于 v 的最小的数的下标
{
    int u = root, res;
    while(u)
    {
        if(tr[u].v >= v) res = u, u = tr[u].s[0];
        else u = tr[u].s[1];
    }
    return res;
}

int get_k(int k) //获取第 k 小数
{
    int u = root;
    while(u)
    {
        if(tr[tr[u].s[0]].cnt >= k) u = tr[u].s[0];
        else if(tr[tr[u].s[0]].cnt + 1 == k) return tr[u].v;
        else k -= tr[tr[u].s[0]].cnt + 1, u = tr[u].s[1];
    }
    return -1;
}

int main()
{
    scanf("%d%d", &n, &minv);

    int l, r;
    l = insert(-INF); //插入左哨兵，并记录位置，在删除员工时会用到
    insert(INF); //插入右哨兵

    int sum = 0; //记录总人数
    while(n--)
    {
        char op[2];
        int k;
        scanf("%s%d", op, &k);

        if(op[0] == 'I')
        {
            if(k >= minv) k -= delta, insert(k), sum++; //每个员工的真实工资 = Splay 中存储的工资 + delta
        }
        else if(op[0] == 'A') delta += k; //所有员工加上 k，即让偏移量加上 k
        else if(op[0] == 'S')
        {
            delta -= k; //所有员工减去 k，即让偏移量减去 k
            r = get(minv - delta); //找到小于最低工资的员工序列的后继，即大于等于最低工资的最小值

            //将小于最低工资的员工序列从 Splay 中删去
            splay(r, 0), splay(l, r);
            tr[l].s[1] = 0;
            pushup(l), pushup(r);
        }
        else
        {
            if(k > tr[root].cnt - 2) puts("-1"); //如果公司员工不足 k 人（去掉两个哨兵），输出 -1
            else printf("%d\n", get_k(tr[root].cnt - k) + delta); //找第 k + 1 大的数（算上左哨兵），等价于找第 tr[root].cnt - k 小的数
        }
    }
    printf("%d\n", sum - (tr[root].cnt - 2)); //离职人数 = 总人数 - 剩余员工数

    return 0;
}