平衡树(FHQ treap) 的一些应用
[郁闷的出纳员]( 郁闷的出纳员 - 洛谷 (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)。
#include using namespace std;const int N = 3e5 + 10; // 定义最大节点数// Treap节点结构体struct node{ int l, r; // 左右子节点索引 int w; // 节点存储的工资值（实际存储的是工资减去累计增量的基础值） int siz; // 以该节点为根的子树大小 int rd; // 随机优先级，用于维护堆性质} tr;int delta; // 工资累计增量（所有员工的工资实际值为存储值 + delta）int cnt; // 节点计数器int root; // 树根节点索引int n, m; // n:操作次数, m:工资下界// 创建新节点int newnode(int x){ tr[++cnt].w = x; // 存储基础工资值 tr.siz = 1; // 初始化子树大小为1 tr.rd = rand(); // 生成随机优先级 return cnt; // 返回新节点索引}// 更新节点子树大小void update(int x){ tr.siz = tr.l].siz + tr.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.w = k) // 左子树节点数足够 p = tr.l; else { if (tr.l) // 如果存在左子树 k -= tr.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.siz) cout
页:
[1]