题解：郁闷的出纳员

一、题目分析

本题中，作为出纳员需要处理员工工资相关事务。老板会对员工工资进行统一的增加或扣除操作，员工工资若低于规定下限会离职，同时公司有新员工入职和老板询问当前工资第(k)多的员工工资等情况。要求编写程序处理这些操作并给出相应结果。

二、解题思路

本题使用Splay树来维护员工工资信息，通过Splay树的基本操作实现对工资数据的插入、查询和调整等功能。

（一）Splay树节点定义

struct Node
{
    int s[2], p, v;
    int size;

    void init(int _v, int _p)
    {
        v = _v, p = _p;
        size = 1;
    }
}tr[N];

定义节点结构体Node，包含左右子节点指针s[2]、父节点指针p、节点值v（表示员工工资）、子树大小size。init函数用于初始化节点。

（二）Splay树基本操作函数

1. 更新节点大小函数pushup：

void pushup(int x)
{
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}

根据左右子树的大小更新当前节点的子树大小。

1. 旋转函数rotate：

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);
}

对节点x进行旋转操作，根据x是其父节点y的左儿子还是右儿子，进行相应的旋转，并更新节点大小。

1. Splay操作函数splay：

void splay(int x, int 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;
}

将节点x通过旋转操作调整到节点k的子节点位置（若k = 0，则调整到根节点）。

（三）插入函数insert

int insert(int v)
{
    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;
}

向Splay树中插入值为v的节点，先找到合适的插入位置，然后插入节点并将其Splay到根节点，返回插入节点的编号。

（四）查找不小于给定值的最小节点函数get

int get(int 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;
}

在Splay树中查找值不小于v的最小节点，通过比较节点值和v，在树中进行搜索并返回相应节点编号。

（五）获取第k小元素值的函数get_k

int get_k(int k)
{
    int u = root;
    while (u)
    {
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k) return tr[u].v;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1;
}

在Splay树中找到第k小的元素值，通过比较左子树大小和k的值，在树中进行搜索并返回元素值。

（六）主函数main

int main()
{
    scanf("%d%d", &n, &m);
    int L = insert(-INF), R = insert(INF);

    int tot = 0;
    while (n -- )
    {
        char op[2];
        int k;
        scanf("%s%d", op, &k);
        if (*op == 'I')
        {
            if (k >= m) k -= delta, insert(k), tot ++ ;
        }
        else if (*op == 'A') delta += k;
        else if (*op == 'S')
        {
            delta -= k;
            R = get(m - delta);
            splay(R, 0), splay(L, R);
            tr[L].s[1] = 0;
            pushup(L), pushup(R);
        }
        else
        {
            if (tr[root].size - 2 < k) puts("-1");
            else printf("%d\n", get_k(tr[root].size - k) + delta);
        }
    }

    printf("%d\n", tot - (tr[root].size - 2));

    return 0;
}

1. 读取操作次数n和工资下限m，插入两个哨兵节点，值分别为-INF和INF，便于处理边界情况。
2. 初始化员工总数tot为(0)，循环处理每一个操作：
   • 若操作符为I（插入新员工工资），当工资不低于下限m时，将工资减去当前调整量delta后插入Splay树，并将员工总数加(1)。
   • 若操作符为A（增加工资），将调整量delta增加k。
   • 若操作符为S（扣除工资），先将调整量delta减去k，然后找到值不小于m - delta的最小节点R，将其Splay到根节点，再将哨兵节点LSplay到R的子节点位置，删除L的右子树（即工资低于下限的员工节点），更新节点大小。
   • 若操作符为F（查询第k多的工资），若树中有效节点数（排除两个哨兵节点）小于k，输出-1；否则通过get_k函数找到第tr[root].size - k小的节点值（因为要找第k多，所以找倒数第k小），加上调整量delta后输出。
3. 最后输出离职员工的数量，即初始记录的员工总数tot减去当前Splay树中有效节点数（排除两个哨兵节点）。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 插入操作：每次插入时间复杂度为(O(\log n))，其中n为Splay树中节点的数量。
• 调整操作（增加或扣除工资）：查找节点、Splay操作等时间复杂度均为(O(\log n))。
• 查询操作：查找第k小元素时间复杂度为(O(\log n))。
• 因此，总的时间复杂度为(O(n\log n))，其中n为操作的总次数。

（二）空间复杂度

代码中使用了数组模拟的Splay树，最多存储员工数量加上两个哨兵节点，所以空间复杂度为(O(N))，N为可能的最大员工数量。