平衡树(FHQ treap) 的一些应用

[郁闷的出纳员]([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