「一本通 4.6 练习 2」郁闷的出纳员

GitHub跳转原题关系图返回列表

全局偏移把全体加减工资压成 O(1)，固定值域上用树状数组按名次答第 k 大，扣薪只扫描长度恰为 k 的阈值区间批量删人。

OJ: roj

题目 ID: 1567

难度:提高

标签:数据结构树状数组python

创建: 2026-09-30 18:51

更新: 2026-10-07 13:50

前置题目

luogu P2234[HNOI2002] 营业额统计B 的 F 命令直接复用 A 教的「在树状数组上用二进制倍增按名次 kth」，把第 k 大转成第 staff-k+1 小后调用同一 kth（main.py 的 kth 与 A 的 kth 逐行同构），只在其上叠加全局偏移 bias 与扣薪区间扫描删除作为新流程。

形式化题目

维护一个工资多重集合 $S$ （初始为空）与统一的工资下界 $min$ ，依次处理 $n$ 条命令：

$I\ k$ ：若 $k \geqslant min$ ，把 $k$ 插入 $S$ ；否则该员工不入职，不计入任何统计。
$A\ k$ ： $S$ 中每个元素加上 $k$ 。
$S\ k$ ： $S$ 中每个元素减去 $k$ ，随后所有 $< min$ 的元素被删除，删除人数计入"离开总数"。
$F\ k$ ：若 $k > |S|$ 则回答 $-1$ ，否则回答 $S$ 中第 $k$ 大的元素。

处理完全部命令后，输出离开总数（不含入职时即低于下界的人）。

样例（ $min = 10$ ）：

text

text

逐命令演进如下，可以同时看到三件事： $A/S$ 只动 $bias$ 、存储值 $x$ 本身几乎不动、离开只发生在 $S$ 抬高阈值的瞬间：

命令	$bias$	在职存储值 $x$ （升序）	实际工资 $x + bias$	输出 / 离开
$I\ 60$	0	60	60
$I\ 70$	0	60, 70	60, 70
$S\ 50$	$-50$	60, 70	10, 20	离开 0 人
$F\ 2$	$-50$	60, 70	10, 20	10
$I\ 30$	$-50$	60, 70, 80	10, 20, 30
$S\ 15$	$-65$	80	15	离开 2 人
$A\ 5$	$-60$	80	20
$F\ 1$	$-60$	80	20	20
$F\ 2$	$-60$	80	20	$-1$

第三次命令的 $S\ 50$ 没有人离开（60、70 减完是 10、20，恰好都不低于 10）；而 $S\ 15$ 把阈值从 60 抬到 75，存储值 60 和 70 对应的实际工资 $-5$ 、 $5$ 都低于 10，两人一起离开，离开总数 2 正是末行输出。

正解

思路

朴素做法与瓶颈。 直接用数组存所有人的工资： $A/S$ 逐个改写数组， $F$ 复制后全排序取第 $k$ 大，离开时线性扫一遍删除。正确，但改写 $O(n)$ 、查询 $O(n\log n)$ ，命令有 $2\times10^5$ 条，总量远超时限。再看一层：朴素解每次都在"把同一个加数加给每个人"上花 $O(n)$ ——而全体加减根本不改变工资之间的相对顺序，这正是优化的入口。

第一步：全局偏移， $A/S$ 降到 $O(1)$ 。 维护 $bias = \sum A - \sum S$ ，员工只存"存储值" $x$ ，实际工资恒为 $x + bias$ 。 $A\ k$ 就是 $bias \mathrel{+}= k$ ， $S\ k$ 就是 $bias \mathrel{-}= k$ ；因为平移不改变顺序，第 $k$ 大实际工资 $=$ 第 $k$ 大存储值 $+ bias$ 。

第二步：删除只扫一个长度为 $k$ 的区间。 $S$ 之后要删掉实际工资 $< min$ 的人，等价于删掉存储值 $x < t = min - bias$ 的人。关键是不变量：在职员工永远满足 $x \geqslant t$ 。插入时只有 $k \geqslant min$ 才建档，故 $x = k - bias \geqslant min - bias = t$ ； $A$ 让 $t$ 变小，不破坏它； $S$ 把 $t$ 抬高后，凡是 $x < t_{new}$ 的人都落在区间 $[t_{old}, t_{new})$ 里，扫描清掉它们，不变量重新成立。而 $bias$ 减了 $k$ 时 $t$ 恰好升 $k$ ，所以每条 $S$ 只需扫描 $k \leqslant 10^3$ 个值——全部命令的扫描总量 $\leqslant 100 \times 10^3 = 10^5$ ，绝不是把所有人重扫一遍。

第三步：值域树状数组顶替平衡树。 剩下的需求是：插入一个人、按名次找第 $k$ 大、把区间内的人数清零。C++ 正解通常上平衡树（splay / treap）；Python 没有内置有序结构，但存储值的值域是固定的： $x = k - bias$ ，由 $0 \leqslant k \leqslant 10^5$ 、 $|bias| \leqslant 10^5$ 得 $x \in [-10^5, 2\times10^5]$ ，只有约 $3\times10^5$ 个整数（ $|bias| \leqslant 10^5$ 来自 $A/S$ 总共不超过 100 条、每条调整量不超过 $10^3$ ）。于是把每个 $x$ 映射到下标 x - X_MIN + 1，用树状数组维护人数前缀和：

插入：cnt[x] 加一，树状数组单点 $+1$ ， $O(\log V)$ ；
$F\ k$ ：第 $k$ 大 $\Leftrightarrow$ 第 $staff - k + 1$ 小，用 binary lifting 在树状数组上按名次二分， $O(\log V)$ ，答案再加回 $bias$ ；
离开：在第二步扫描到的每个位置上取回 cnt[x]，树状数组单点减掉人数。

于是四类命令全部 $O(\log V)$ 或更便宜，总复杂度 $O((n + \sum k_S)\log V)$ ，与平衡树正解同阶。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 18:51
# update_at: 2026-09-30 18:54

import sys

X_MIN = -100_000  # 存储值 x = 实际工资 - bias 的理论下界：k ≥ 0、bias ≤ 1e5
X_MAX = 200_000  # 理论上界：k ≤ 1e5、bias ≥ -1e5
POS_SIZE = X_MAX - X_MIN + 2  # 树状数组下标 1..POS_SIZE-1，比值域多留 1 位

TREE = [0] * POS_SIZE  # 树状数组：按存储值 x 的名次统计人数


def update(pos: int, delta: int) -> None:
    """树状数组第 pos 个下标增减 delta 人（pos 从 1 开始）。"""
    while pos < POS_SIZE:
        TREE[pos] += delta
        pos += pos & -pos


def kth(rank: int) -> int:
    """最小的下标 pos，使前缀人数 ≥ rank；rank 从 1 开始，即第 rank 小。"""
    pos = 0
    step = 1 << (POS_SIZE.bit_length() - 1)  # 不小于 POS_SIZE 的最高 2 次幂
    while step:
        nxt = pos + step
        if nxt < POS_SIZE and TREE[nxt] < rank:
            pos = nxt
            rank -= TREE[nxt]
        step >>= 1
    return pos + 1


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))  # 命令条数
    floor = int(next(data))  # 工资下界 min

    cnt: dict[int, int] = {}  # 每个存储值 x 当前的人数
    staff = 0  # 在职人数，等于树状数组总和
    bias = 0  # 全局偏移：实际工资 = 存储值 x + bias，A/S 只改它
    leave = 0  # 因扣薪低于下界离开的人数（不含入职即低于下界者）
    out: list[str] = []

    for _ in range(n):
        cmd = next(data)
        k = int(next(data))

        if cmd == b'I':
            # 入职即低于下界的直接走人：不建档也不计入离开总数
            if k >= floor:
                x = k - bias  # 存储值，保证不变量：所有在职 x ≥ floor - bias
                cnt[x] = cnt.get(x, 0) + 1
                staff += 1
                update(x - X_MIN + 1, 1)

        elif cmd == b'A':
            bias += k  # 全员加薪：只抬偏移，无人低于下界

        elif cmd == b'S':
            bias -= k
            # 下界阈值 t = floor - bias 随扣薪恰好抬高 k；由不变量只需扫描 [t-k, t)
            hi = floor - bias
            for x in range(max(hi - k, X_MIN), min(hi, X_MAX + 1)):
                gone = cnt.pop(x, 0)  # 区间内不在职的值弹出为 0，不影响结果
                if gone:
                    staff -= gone
                    leave += gone
                    update(x - X_MIN + 1, -gone)

        else:  # F k：第 k 大的工资，等价于第 staff-k+1 小的存储值
            if k > staff:
                out.append("-1")
            else:
                x = kth(staff - k + 1) - 1 + X_MIN  # 名次二分回存储值
                out.append(str(x + bias))  # 平移回实际工资

    out.append(str(leave))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:50
 * update_at: 2026-10-05 08:50
 */

// 正解：全局偏移 + 值域树状数组（名次二分求第 k 大）+ 扣薪时只扫长度为 k 的阈值区间。
// 实际工资 = 存储值 x + bias，A/S 只改 bias；
// 不变量：在职者的存储值 x >= t = min - bias（入职时 k >= min 保证，扣薪后即时清理破坏者）。

#include <cstdio>

typedef long long ll;

const int X_MIN = -100000;             // 存储值下界：k >= 0、bias <= 1e5
const int X_MAX = 200000;              // 存储值上界：k <= 1e5、bias >= -1e5
const int POS_SIZE = X_MAX - X_MIN + 2; // 树状数组下标 1..POS_SIZE-1，比值域多留 1 位

ll mn;            // 工资下界 min
ll bias = 0;      // 全局偏移：实际工资 = 存储值 x + bias，A/S 只改它
ll staff_num = 0; // 在职人数，等于树状数组总和
ll leave = 0;     // 因扣薪低于下界离开的总数（不含入职即低于下界者）
ll cnt[POS_SIZE]; // 原数组：cnt[pos] = 存储值 x = pos + X_MIN - 1 当前的人数
ll tree[POS_SIZE]; // 树状数组：按存储值名次维护人数前缀和

// 树状数组第 pos 个下标增减 delta 人
void update(int pos, ll delta) {
    for (; pos < POS_SIZE; pos += pos & (-pos))
        tree[pos] += delta;
}

// 树状数组上名次二分：返回第 rank 小者的树状数组下标（rank 从 1 开始）
// 经典 binary lifting：从高位往低位试跳，走到"前缀人数 < rank"的最右位置
int kth(ll rank) {
    int pos = 0;
    for (int step = 1 << 18; step >= 1; step >>= 1) { // 2^18 > POS_SIZE，足够跳全程
        int nxt = pos + step;
        if (nxt < POS_SIZE && tree[nxt] < rank) {
            pos = nxt;
            rank -= tree[nxt];
        }
    }
    return pos + 1; // 第 rank 小者所在下标
}

// 处理一条 S 命令：bias 降 k 后，阈值 t = mn - bias 恰好升高 k，
// 由不变量"旧在职者都 >= t - k"，只需扫描存储值区间 [t-k, t)，
// 把其中还挂着的人全部清掉，其余人一定仍合法
void do_s(ll k) {
    bias -= k;
    ll hi = mn - bias;  // 新阈值 t（存储值视角，左闭右开的右端点）
    ll lo = hi - k;     // 旧阈值，旧在职者都 >= lo
    if (lo < X_MIN)
        lo = X_MIN;
    if (hi > (ll)X_MAX + 1)
        hi = X_MAX + 1;
    for (ll x = lo; x < hi; ++x) { // 左闭右开：只扫恰好这一段
        int pos = int(x - X_MIN + 1);
        ll gone = cnt[pos];        // 该存储值上在职的人数
        if (gone > 0) {
            cnt[pos] = 0;
            staff_num -= gone;
            leave += gone;
            update(pos, -gone);    // 树状数组同步减掉这些人
        }
    }
}

int main() {
    ll n;
    scanf("%lld %lld", &n, &mn);
    for (ll t = 1; t <= n; ++t) {
        char op[4];
        ll k;
        scanf("%s %lld", op, &k);
        if (op[0] == 'I') {
            // 入职即低于下界：不建档也不计入离开总数
            if (k >= mn) {
                int pos = int(k - bias - X_MIN + 1);
                cnt[pos]++;
                staff_num++;
                update(pos, 1);
            }
        } else if (op[0] == 'A') {
            bias += k; // 全员加薪：只抬偏移，不会有人低于下界
        } else if (op[0] == 'S') {
            do_s(k);
        } else { // F k：第 k 大 = 第 staff-k+1 小的存储值
            if (k > staff_num) {
                printf("-1\n");
            } else {
                int pos = kth(staff_num - k + 1);
                ll x = pos + X_MIN - 1;        // 名次二分回存储值
                printf("%lld\n", x + bias);    // 平移回实际工资
            }
        }
    }
    printf("%lld\n", leave);
    return 0;
}

复杂度

时间复杂度： $O((n + \sum k_S)\log V)$ ，其中 $V = 3\times10^5 + 1$ 是值域， $n \leqslant 2\times10^5$ 是命令数， $\sum k_S \leqslant 10^5$ 是所有 $S$ 命令的扫描总量；与 C++ 平衡树解法同阶。
空间复杂度： $O(V + n)$ ：树状数组 $3\times10^5$ 个整数加 cnt 字典至多 $n$ 项；实测峰值 42.1 MB，限制 128 MB。

总结

这道题的三个观察各消除一层成本：全体加减用全局偏移收成 $O(1)$ ；扣薪删除靠"在职者 $x \geqslant t$ "这条不变量收成长度恰为 $k$ 的区间扫描；剩下的插入与第 $k$ 大查询落在固定值域上，用树状数组的名次二分顶替平衡树。实现上只有一个易错点——删除必须左闭右开扫到 $t_{new}$ 之前、且 $F$ 先判 $k \leqslant staff$ 再二分。实测 10 组真实数据全部一致，单点最慢 0.204 s、峰值 42.1 MB，相对 1000 ms / 128 MB 的限制十分宽裕。

【题目描述】

原题来自：NOI 2004

OIER 公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候。一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第 $k$ 多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

【输入】

第一行有两个非负整数 $n$ , $min$ ， $n$ 表示下面有多少条命令， $min$ 表示工资的下界；

接下来的 $n$ 行，每行表示一个命令。命令可以是以下四种之一：

名称

格式

作用

$I$ 命令

$I\\ k$

新建一个工资档案，初始工资为 $k$ 。如果某员工的初始工资低于工资下界，他将立刻离开公司。

$A$ 命令

$A\\ k$

把每位员工的工资加上 $k$ 。

$S$ 命令

$S\\ k$

把每位员工的工资扣除 $k$ 。

$F$ 命令

$F\\ k$

查询第 $k$ 多的工资。

$I$ 命令， $A$ 命令， $S$ 命令中， $k$ 是一个非负整数。 $F$ 命令中， $k$ 是一个正整数。

在初始时，可以认为公司中一位员工也没有。

【输出】

输出的行数为 $F$ 命令的条数加一。

对于每条 $F$ 命令，你的程序要输出一行，仅包含一个整数，为当前工资第 $k$ 多的员工所拿的工资数，如果 $k$ 大于目前员工的数目，则输出 $-1$ ；

输出的最后一行包含一个整数，为离开公司的员工的总数（不包括因员工的初始工资低于工资下界而离开公司的情况）。

【输入样例】

text

【输出样例】

text

【提示】

数据范围与提示：

对于全部数据， $I$ 命令的条数不超过 $10^5$ ， $A$ 命令和 $S$ 命令的总条数不超过 $100$ ， $F$ 命令的条数不超过 $10^5$ 。

每次工资调整的调整量不超过 $10^3$ ，新员工的工资不超过 $10^5$ 。

【来源】

一本通在线评测

「一本通 4.6 练习 2」郁闷的出纳员

目录

形式化题目

正解

思路

代码

复杂度

总结