把序列摊到足够长的坐标轴上,用树状数组记坐标占用:Top/Bottom 占两端空位,Insert 只换坐标,Ask/Query 化为前缀和与第 k 个 1。
OJ: roj
题目 ID: 1992
难度:提高+/省选-
标签:树状数组平衡树python
创建: 2026-10-08 06:46
更新: 2026-10-08 06:46
形式化题目
维护一个长为
Top S:把编号为的书移到序列最前面; Bottom S:把编号为的书移到序列最后面; Insert S T():把编号为 的书的位置平移 ,即它的排名从 变成 ; Ask S:输出编号为的书当前排名减一(即它上面有多少本书); Query S:输出当前排名为的书的编号。
保证在 Insert S -1,在 Insert S 1;
注意 Query S 的参数与 Ask S 的参数语义不同:前者是排名,后者是书的编号。
两者互为逆运算,所以任何做法都必须同时支持"由编号查排名"和"由排名查编号"两个方向。
正解
思路
朴素做法。 用一个数组(或 vector)直接存序列。那么 Query S 是 Top / Bottom 要整体挪动 Ask S 要么 Ask 沿链数前缀、Query 找第
瓶颈的根源是"位置会变"这个假象。 真正观测到的现象是:五种命令只让书在首、尾、相邻三处挪动, 没有任何命令要求把书搬进序列中段的一个陌生位置。这提示我们不必维护"动态下标", 可以反过来把书钉在静态坐标上。
关键观察一:坐标轴足够长时,所有位置变化都能当静态坐标处理。
把每本书放在一根坐标轴上的某个位置
- 初始时第
本书放在 ,其中 ,左边留 格、右边留 格; - 维护左游标
lo与右游标hi。Top S把的坐标改成 --lo,Bottom S改成++hi; Insert S T干脆只交换两本书的坐标——序列顺序变了,但用到的坐标集合一字未动。
由于 Top 至多发生 lo 最多左移 Bottom 同理最多右移
关键观察二:坐标一旦静态,两种查询都变成"一维数点"。
设
前一个式子是前缀和,后一个是"第
| 命令 | 实现 |
|---|---|
Top S |
坐标 add(p, -1),--lo 后 add(lo, 1),同时改 pos / rev |
Bottom S |
同上,把 --lo 换成 ++hi |
Insert S T |
先 k = prefix(pos[S]);目标坐标 |
Ask S |
prefix(pos[S] - 1) |
Query S |
rev[select(S)],select 是第 |
Insert 是这里最漂亮的一步:整条命令读作"p + t,必须先算出 pos、rev 两张表和实际序列一致,
而
为什么"第 prefix 判够不够,
一个
与平衡树做法的关系。 本题的常见正解是 Splay(或 FHQ-Treap)维护中序遍历为书架序列:
Ask 靠把节点旋到根后取左子树大小,Insert 靠与中序前驱/后继交换节点内保存的书号,
Top / Bottom 靠断链重挂。对比之下,树状数组做法把"树的形状"彻底换成了"一根静态坐标轴",
省掉了旋转、父子指针、子树大小这些必须小心维护的状态——Insert 的"交换编号"技巧
在两边都出现了,只不过这里交换的是坐标而不是节点键值。
代码
Python 版:
#!/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-10-08 06:46
# update_at: 2026-10-08 06:46
import sys
from collections.abc import Iterator
SIZE = 2 * 80005 + 80005 + 10 # 坐标轴长度:m 个顶部空位 + n 本书 + m 个底部空位
TOP_CMD = b"Top"
BOTTOM_CMD = b"Bottom"
INSERT_CMD = b"Insert"
ASK_CMD = b"Ask"
QUERY_CMD = b"Query"
def add(bit: list[int], x: int, delta: int) -> None:
"""坐标 x 上的书本数加 delta(树状数组单点修改)。"""
while x < SIZE:
bit[x] += delta
x += x & -x
def prefix(bit: list[int], x: int) -> int:
"""坐标 <= x 的书本数量,也就是坐标 x 上那本书的排名。"""
total = 0
while x > 0:
total += bit[x]
x -= x & -x
return total
def select(bit: list[int], k: int) -> int:
"""第 k 个 1 所在的坐标(BIT 上倍增,比"二分 + 前缀和"少一个 log)。"""
x = 0
step = 1 << 18 # 2^18 = 262144 > SIZE,从最高位往下试
while step:
if x + step < SIZE and bit[x + step] < k:
x += step
k -= bit[x]
step >>= 1
return x + 1
def simulate(data: Iterator[bytes]) -> list[str]:
"""按命令流模拟书架,按顺序返回所有 Ask / Query 的答案行。
序列被摊在一根足够长的坐标轴上:Top 只会占用不断左移的空位,
Bottom 只会占用不断右移的空位,Insert 只交换两本书的坐标,
因此"位置"始终可以当成静态坐标来用,不需要任何平衡树。
"""
n = int(next(data))
m = int(next(data))
bit = [0] * SIZE # bit: 坐标 x 上是否有书(树状数组)
rev = [0] * SIZE # rev[x] = 坐标 x 上的书编号,0 表示空位
pos = [0] * (n + 1) # pos[v] = 书 v 当前的坐标
base = m + 5 # 初始书堆的起点,左边留 m 格给 Top,右边留 m 格给 Bottom
for i in range(1, n + 1):
v = int(next(data))
x = base + i
pos[v] = x
rev[x] = v
add(bit, x, 1)
lo = base # 下一次 Top 的落点,每次左移一格
hi = base + n # 下一次 Bottom 的落点,每次右移一格
out: list[str] = []
for _ in range(m):
op = next(data)
s = int(next(data))
if op == TOP_CMD: # Top S:把 S 搬到最上面
p = pos[s]
add(bit, p, -1)
rev[p] = 0
lo -= 1
pos[s] = lo
rev[lo] = s
add(bit, lo, 1)
elif op == BOTTOM_CMD: # Bottom S:把 S 搬到最下面
p = pos[s]
add(bit, p, -1)
rev[p] = 0
hi += 1
pos[s] = hi
rev[hi] = s
add(bit, hi, 1)
elif op == INSERT_CMD: # Insert S T:与排名相差 T 的那本书换坐标
t = int(next(data))
if t == 0:
continue
p = pos[s]
rank = prefix(bit, p) # S 当前的 1-indexed 排名
q = select(bit, rank + t) # 排名相差 t 的那本书的坐标
other = rev[q]
rev[p] = other # 两本书互换坐标:坐标集合没变,BIT 无需改动
rev[q] = s
pos[other] = p
pos[s] = q
elif op == ASK_CMD: # Ask S:S 上面有多少本书
answer = prefix(bit, pos[s] - 1)
out.append(str(answer))
elif op == QUERY_CMD: # Query S:从上数第 S 本书的编号
answer = rev[select(bit, s)]
out.append(str(answer))
return out
def solve() -> None:
out = simulate(iter(sys.stdin.buffer.read().split()))
if out: # 一条 Ask/Query 都没有时不能多打一个空行
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-08 06:46
* update_at: 2026-10-08 06:46
*/
// 1992 书架book(同 [ZJOI2006] 书架 / 洛谷 P2596)
//
// 算法:树状数组(BIT)维护“位置是否被占” + 每个书编号映射到具体位置。
//
// 关键观察:Top / Bottom 只会把书放到序列的首/尾,Insert 只在相邻位置之间交换,
// 因此可以把整个序列摆进一个“足够宽的连续坐标轴”里:
// - 初始时第 i 本书放在坐标 BASE + i 处,BASE 上方预留下 m 个空位;
// - Top S : 把 S 搬到当前左侧游标 lo 处(lo 每次左移一格);
// - Bottom S : 把 S 搬到当前右侧游标 hi 处(hi 每次右移一格);
// - Insert S T: 与“排名相差 T 的那本书”直接交换坐标(坐标集合不变,BIT 不用动);
// - Ask S : S 的排名 = 坐标 <= pos[S] 的书本数量,即 BIT 前缀和;
// - Query S : BIT 上二分(倍增)找第 S 个 1 所在坐标,再查该坐标上的书。
// 每个操作都是 O(log n),总复杂度 O((n + m) log n)。
//
// 复杂度之上还有一层常量优势:BIT 的常数远小于平衡树,n, m <= 8e4 时非常轻松。
#include <cstdio>
const int MAXN = 80005;
const int MAXM = 80005;
const int MAXP = 2 * MAXM + MAXN + 10; // 坐标轴长度:预留 m 个顶部空位 + n 本书 + m 个底部空位
typedef long long ll;
int n, m;
int bit[MAXP]; // 树状数组:坐标 x 上有没有书
int rev[MAXP]; // rev[x] = 坐标 x 上的书的编号(0 表示空位)
int pos[MAXN]; // pos[v] = 书 v 当前所在坐标
int lo, hi; // lo: 下一次 Top 使用的坐标;hi: 下一次 Bottom 使用的坐标
// 树状数组单点加减
void add(int x, int delta) {
for (; x < MAXP; x += x & -x) bit[x] += delta;
}
// 树状数组前缀和:坐标 <= x 的书本数量
int sum(int x) {
int s = 0;
for (; x > 0; x -= x & -x) s += bit[x];
return s;
}
// 倍增求第 k 个 1 所在的坐标(k 从 1 开始)
int kth(int k) {
int x = 0;
for (int step = 1 << 18; step; step >>= 1) { // 2^18 > MAXP,从大到小倍增
if (x + step < MAXP && bit[x + step] < k) {
x += step;
k -= bit[x];
}
}
return x + 1;
}
int main() {
scanf("%d %d", &n, &m);
const int BASE = m + 5; // 初始书堆的起点:左边留 m 格给 Top,右边留 m 格给 Bottom
for (int i = 1; i <= n; i++) {
int v;
scanf("%d", &v);
int x = BASE + i;
pos[v] = x;
rev[x] = v;
add(x, 1);
}
lo = BASE;
hi = BASE + n;
char op[16];
for (int i = 0; i < m; i++) {
int s, t = 0;
scanf("%s %d", op, &s);
if (op[0] == 'T') { // Top S:搬到最上面
int p = pos[s];
add(p, -1);
rev[p] = 0;
lo--;
pos[s] = lo;
rev[lo] = s;
add(lo, 1);
} else if (op[0] == 'B') { // Bottom S:搬到最下面
int p = pos[s];
add(p, -1);
rev[p] = 0;
hi++;
pos[s] = hi;
rev[hi] = s;
add(hi, 1);
} else if (op[0] == 'I') { // Insert S T:与排名相差 T 的书交换坐标
scanf("%d", &t);
if (t == 0) continue;
int p = pos[s];
int k = sum(p); // s 当前的 1-indexed 排名
int q = kth(k + t); // 相邻的那本书的坐标
int other = rev[q];
// 两本书互换坐标:坐标集合没变,所以 BIT 不需要改动
rev[p] = other;
rev[q] = s;
pos[other] = p;
pos[s] = q;
} else if (op[0] == 'A') { // Ask S:S 上面有多少本书
printf("%d\n", sum(pos[s] - 1));
} else { // Query S:从上数第 S 本书的编号
printf("%d\n", rev[kth(s)]);
}
}
return 0;
}复杂度
- 时间:建表
;每条命令都是常数次树状数组操作,每次 。 总计 ,取 约 次基本运算。C++ 实测最大点( )约 0.02 s(限时 1000 ms)。 - 空间:树状数组、
rev各长, pos长, 全为整型数组,约 KB,远低于 128 MB。 - 与 C++ 解法的关系:
main.py与main.cpp是逐行对应的同一算法, 同样用prefix/select两个函数支撑五种命令。Python 单次操作是解释执行的循环, 在规模下比 C++ 慢一到两个数量级,属于本仓库允许的 Python 侧 TLE 风险, 但算法复杂度与 C++ 完全同阶,没有把任何一步降级成暴力枚举。
总结
- "位置会变"往往是伪需求:先问清楚位置的变化范围有多大。本题的书只会去首、尾和相邻位置, 于是可以把位置换成一根静态坐标轴上的标签,动态结构(平衡树)直接退化为静态结构(树状数组)。
- 两端留够空位:
Top/Bottom各至多次,所以初始书堆左右各留 格就够; 这类"预留游标空间"的技巧在线段树合并、栈式模拟里同样常见。 Insert只交换数据、不搬结构:排名相邻的两本书互换坐标后,c(\cdot)集合不变, 一次交换顶掉了插入 + 删除的两次更新。平衡树版本里的"交换节点键值"是同一思想的另一种表达。- 两个方向要一起想:
Ask是"由编号查排名",Query是"由排名查编号", 树状数组的前缀和与"第个 1"恰好一对一,这也是选择树状数组而非线段树的原因(更短、更快)。 - 倍增求第
个 1:把 降到 ,是树状数组的固定套路, 值得当作模板记住。
数据说明
- 本题即洛谷 P2596「[ZJOI2006] 书架」/ BZOJ1861「Book 书架」,题面与数据范围
(
、 Insert的)与原题一致。 - 素材源的
std.cpp用的是数组版 Splay(pos[]把书号映射到节点,Insert与中序前驱/后继 交换节点内保存的书号);本文的树状数组解法与之独立,两者在全部 10 组数据上输出一致, 可互为交叉验证。 - 本目录的
data/由随题提供的生成脚本(data.py)自动生成,属于自造数据, 题面亦为按公开页面重建;因此出题意图与官方原题可能存在细节偏差, 但本解的所有结论均已在该 10 组数据上逐点验证通过。 - 题面所给样例共 6 个输出,
main.cpp与main.py均逐一匹配; 额外用固定种子的随机小数据与vector暴力解做了对拍(C++ 累计 292 组、Python 累计 264 组, 覆盖的最小规模、 的中等规模与 Top/Bottom反复重排), 另外还与素材源的 Splay 解做了 61 组三方交叉验证,全部一致。 还用、 的极端数据(几乎全是 Top/Bottom)验证了 “两端各留格”确实是紧的:左游标最低恰好降到坐标 ,仍在数组范围内, 且 C++ 与 Python 输出完全一致。
图示解析
下图重演题面样例。样例 Query 3、Top 5、Ask 6、Bottom 3、Ask 3、Top 6、Insert 4 -1、
Query 5、Query 2、Ask 2。
flowchart TD
S0["初始:坐标 16..25 依次放 1 3 2 7 5 8 10 4 9 6,lo=15,hi=25"] --> S1
S1["Query 3 → 第 3 个 1 的坐标是 18 → rev[18] = 2,输出 2"] --> S2
S2["Top 5:20 处抹掉,lo 左移到 14,5 落到 14<br/>序列 5 1 3 2 7 8 10 4 9 6"] --> S3
S3["Ask 6 → prefix(24) = 9,输出 9"] --> S4
S4["Bottom 3:17 处抹掉,hi 右移到 26,3 落到 26<br/>序列 5 1 2 7 8 10 4 9 6 3"] --> S5
S5["Ask 3 → prefix(25) = 9,输出 9"] --> S6
S6["Top 6:25 处抹掉,lo 左移到 13,6 落到 13<br/>序列 6 5 1 2 7 8 10 4 9 3"] --> S7
S7["Insert 4 -1:4 在坐标 23,rank(4) = prefix(23) = 8<br/>目标 = 第 7 个 1 的坐标 22(书 10),交换两者"] --> S8
S8["交换坐标 22 与 23 的内容 → 6 5 1 2 7 8 4 10 9 3<br/>坐标集合没变,BIT 一个格子都没动"] --> S9
S9["Query 5 → rev[第 5 个 1 的坐标 19] = 7,输出 7<br/>Query 2 → 5;Ask 2 → prefix(17) = 3"]
读图要点有三处。第一,lo 与 hi 是两根游标:Top 用左侧空位、Bottom 用右侧空位,
两者各至多移动 Ask S 是对 pos[S] 做一次
前缀和,Query S 是在同一个 BIT 上找第 Insert 只交换两本书的坐标标签,只要 pos / rev 保持一致、
样例里的 Insert 4 -1 跟踪下来恰好是:4 在坐标 23,它的排名是 prefix(23) = 8,
第 p - 1 也能对;但 Top / Bottom 在坐标轴上
挖出空位后,排名相邻的两本书坐标就会隔开。
这不是纸上推演,而是实测过的:把 main.py 里那行换成 q = p + t(“坐标直接加 Insert 配了 Top / Bottom,
坐标轴上从未出现空位。所以“先 prefix 定出排名,再取第
上面这条坐标轨迹是用真实程序逐行回放核对的(坐标 22 上的书确实是 10),不是纸上推演。