[郁闷的出纳员]([P1486 NOI2004] 郁闷的出纳员 - 洛谷 (luogu.com.cn))
代功能说明：
- 数据结构：使用无旋Treap维护员工工资信息
- 核心变量：
- delta：累计工资增量（所有员工的工资实际值 = 存储值 + delta）
- m：工资下界（低于此值的员工会被移除）
- leave：记录因降薪离开的员工总数
- 操作解释：
- 插入(I)：仅当工资≥m时才插入（存储基础值 = 实际工资 - delta）
- 涨薪(A)：增加delta值（影响所有员工）
- 降薪(S)：
- 减少delta值
- 移除所有基础值 ≤ (m - delta - 1)的员工（即实际工资 < m）
- 累加离开员工数到leave
- 查询(F)：查询第k高工资（实际值 = 存储值 + delta）
- 若k大于当前员工数，输出-1
- 通过查找第(总人数-k+1)小节点实现
- 关键技巧：
- 通过维护delta避免频繁更新所有节点
- 降薪时通过Treap分割高效移除低工资员工
- 查询时通过子树大小快速定位第k大元素
该实现高效处理了动态工资调整和员工淘汰机制，时间复杂度主要操作均为O(log n)。
[code]#include using namespace std;const int N = 3e5 + 10; // 定义最大节点数// Treap节点结构体struct node{ int l, r; // 左右子节点索引 int w; // 节点存储的工资值（实际存储的是工资减去累计增量的基础值） int siz; // 以该节点为根的子树大小 int rd; // 随机优先级，用于维护堆性质} tr[N];int delta; // 工资累计增量（所有员工的工资实际值为存储值 + delta）int cnt; // 节点计数器int root; // 树根节点索引int n, m; // n:操作次数, m:工资下界// 创建新节点int newnode(int x){ tr[++cnt].w = x; // 存储基础工资值 tr[cnt].siz = 1; // 初始化子树大小为1 tr[cnt].rd = rand(); // 生成随机优先级 return cnt; // 返回新节点索引}// 更新节点子树大小void update(int x){ tr[x].siz = tr[tr[x].l].siz + tr[tr[x].r].siz + 1;}// 按值分割Treap：将树p按值k分割成两棵树x和y（x中所有节点值k）void split(int p, int k, int &x, int &y){ if (!p) { x = y = 0; return; } if (tr[p].w = k) // 左子树节点数足够 p = tr[p].l; else { if (tr[p].l) // 如果存在左子树 k -= tr[tr[p].l].siz; // 减去左子树节点数 k--; // 减去当前节点 if (!p || k > n >> m; for (int i = 1; i > opt >> k; if (opt == 'I') // 插入操作 { // 如果工资低于下界m，直接跳过 if (k < m) continue; // 存储基础值 = 实际工资 - 当前累计增量delta k -= delta; // 按值k分割树 split(root, k, x, y); // 创建新节点并合并树 root = merge(x, merge(newnode(k), y)); } else if (opt == 'A') // 全体涨薪 delta += k; else if (opt == 'S') // 全体降薪 { delta -= k; // 分割树：x树包含所有工资低于新下界的员工（基础值 tr[root].siz) cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
