书架book

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

把序列摊到足够长的坐标轴上,用树状数组记坐标占用:Top/Bottom 占两端空位,Insert 只换坐标,Ask/Query 化为前缀和与第 k 个 1。

OJ: roj

题目 ID: 1992

难度:提高+/省选-

标签:树状数组平衡树python

创建: 2026-10-08 06:46

更新: 2026-10-08 06:46

形式化题目

维护一个长为 nn 的序列 q1,q2,…,qnq_1, q_2, \dots, q_n(qq 是 1∼n1 \sim n 的排列,qiq_i 表示从上往下第 ii 本书的编号)。 依次处理 mm 条命令,命令共五种:

  • Top S:把编号为 SS 的书移到序列最前面;
  • Bottom S:把编号为 SS 的书移到序列最后面;
  • Insert S T(T∈{−1,0,1}T \in \{-1, 0, 1\}):把编号为 SS 的书的位置平移 TT,即它的排名从 kk 变成 k+Tk + T;
  • Ask S:输出编号为 SS 的书当前排名减一(即它上面有多少本书);
  • Query S:输出当前排名为 SS 的书的编号。

保证在 SS 已在首位时不会出现 Insert S -1,在 SS 已在末位时不会出现 Insert S 1; 3⩽n,m⩽8×1043 \leqslant n, m \leqslant 8 \times 10^4,要求 10001000 ms 内完成。

注意 Query S 的参数与 Ask S 的参数语义不同:前者是排名,后者是书的编号。 两者互为逆运算,所以任何做法都必须同时支持"由编号查排名"和"由排名查编号"两个方向。

正解

思路

朴素做法。 用一个数组(或 vector)直接存序列。那么 Query S 是 O(1)O(1) 的,但 Top / Bottom 要整体挪动 Θ(n)\Theta(n) 个元素,Ask S 要么 O(n)O(n) 线性找、翻位, 要么额外维护一个"编号 →\to 位置"的映射,而一旦有书插到中间,映射里成千上万条记录全要改。 换成双向链表能 O(1)O(1) 地挪节点、靠映射 O(1)O(1) 地定位,但 Ask 沿链数前缀、Query 找第 kk 个 都退化成 O(n)O(n)。两种结构都只能覆盖一半的操作,总复杂度 O(nm)O(nm) 在 8×1048 \times 10^4 下必然超时。

瓶颈的根源是"位置会变"这个假象。 真正观测到的现象是:五种命令只让书在首、尾、相邻三处挪动, 没有任何命令要求把书搬进序列中段的一个陌生位置。这提示我们不必维护"动态下标", 可以反过来把书钉在静态坐标上。

关键观察一:坐标轴足够长时,所有位置变化都能当静态坐标处理。 把每本书放在一根坐标轴上的某个位置 xx,位置只是标签、不要求稠密。预先留出两端空间:

  • 初始时第 ii 本书放在 x=base+ix = \text{base} + i,其中 base=m+5\text{base} = m + 5,左边留 mm 格、右边留 mm 格;
  • 维护左游标 lo 与右游标 hi。Top S 把 SS 的坐标改成 --lo,Bottom S 改成 ++hi;
  • Insert S T 干脆只交换两本书的坐标——序列顺序变了,但用到的坐标集合一字未动。

由于 Top 至多发生 mm 次,lo 最多左移 mm 格;Bottom 同理最多右移 mm 格。 两端各留 mm 格刚好够用,不会撞车。

关键观察二:坐标一旦静态,两种查询都变成"一维数点"。 设 c(x)=1c(x) = 1 表示坐标 xx 上有书、00 表示空位,那么

rank(S)=∑x′⩽xSc(x′),第 k 名的书=坐标轴上第 k 个 1 处的书.\text{rank}(S) = \sum_{x' \leqslant x_S} c(x'), \qquad \text{第 } k \text{ 名的书} = \text{坐标轴上第 } k \text{ 个 } 1 \text{ 处的书}.

前一个式子是前缀和,后一个是"第 kk 个 1",两者正好是树状数组的两个标准操作:

命令 实现
Top S 坐标 p=pos[S]p = pos[S] 处 add(p, -1),--lo 后 add(lo, 1),同时改 pos / rev
Bottom S 同上,把 --lo 换成 ++hi
Insert S T 先 k = prefix(pos[S]);目标坐标 qq 是第 k+Tk+T 个 11;交换 p,qp, q 上的两本书
Ask S prefix(pos[S] - 1)
Query S rev[select(S)],select 是第 SS 个 11 的坐标

Insert 是这里最漂亮的一步:整条命令读作"SS 的排名加 TT",而排名紧邻的两本书 在坐标轴上不一定相邻(中间可能夹着空位)。所以不能写 p + t,必须先算出 SS 的排名 再找第 k+Tk + T 个 1,拿到 qq 以后互换。互换之后 pos、rev 两张表和实际序列一致, 而 c(⋅)c(\cdot) 集合未变,树状数组一个格子都不用改。

为什么"第 kk 个 1"用倍增而不是二分。 朴素写法是二分坐标区间、每次 prefix 判够不够, 一个 log⁡\log 之外再套一个 log⁡\log,变成 O(log⁡2n)O(\log^2 n)。树状数组上直接倍增可以一次扫完: 从最高位 2182^{18}(大于坐标轴长度)往下试,若 x+2jx + 2^j 处的前缀和仍小于 kk 就跳过去, 跳出后 x+1x + 1 就是答案。整个过程恰好在 O(log⁡n)O(\log n) 内完成,且常数极小。

与平衡树做法的关系。 本题的常见正解是 Splay(或 FHQ-Treap)维护中序遍历为书架序列: Ask 靠把节点旋到根后取左子树大小,Insert 靠与中序前驱/后继交换节点内保存的书号, Top / Bottom 靠断链重挂。对比之下,树状数组做法把"树的形状"彻底换成了"一根静态坐标轴", 省掉了旋转、父子指针、子树大小这些必须小心维护的状态——Insert 的"交换编号"技巧 在两边都出现了,只不过这里交换的是坐标而不是节点键值。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:建表 O(nlog⁡n)O(n \log n);每条命令都是常数次树状数组操作,每次 O(log⁡(SIZE))=O(log⁡(n+m))O(\log(\text{SIZE})) = O(\log(n+m))。 总计 O((n+m)log⁡(n+m))O((n + m) \log(n + m)),取 n=m=8×104n = m = 8 \times 10^4 约 1.6×105×19≈3×1061.6 \times 10^5 \times 19 \approx 3 \times 10^6 次基本运算。C++ 实测最大点(n=m=8×104n = m = 8 \times 10^4)约 0.02 s(限时 1000 ms)。
  • 空间:树状数组、rev 各长 SIZE=2m+n+10\text{SIZE} = 2m + n + 10,pos 长 n+1n + 1, 全为整型数组,约 650650 KB,远低于 128 MB。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是逐行对应的同一算法, 同样用 prefix / select 两个函数支撑五种命令。Python 单次操作是解释执行的循环, 在 8×1048 \times 10^4 规模下比 C++ 慢一到两个数量级,属于本仓库允许的 Python 侧 TLE 风险, 但算法复杂度与 C++ 完全同阶,没有把任何一步降级成暴力枚举。

总结

  • "位置会变"往往是伪需求:先问清楚位置的变化范围有多大。本题的书只会去首、尾和相邻位置, 于是可以把位置换成一根静态坐标轴上的标签,动态结构(平衡树)直接退化为静态结构(树状数组)。
  • 两端留够空位:Top / Bottom 各至多 mm 次,所以初始书堆左右各留 mm 格就够; 这类"预留游标空间"的技巧在线段树合并、栈式模拟里同样常见。
  • Insert 只交换数据、不搬结构:排名相邻的两本书互换坐标后,c(\cdot) 集合不变, 一次交换顶掉了插入 + 删除的两次更新。平衡树版本里的"交换节点键值"是同一思想的另一种表达。
  • 两个方向要一起想:Ask 是"由编号查排名",Query 是"由排名查编号", 树状数组的前缀和与"第 kk 个 1"恰好一对一,这也是选择树状数组而非线段树的原因(更短、更快)。
  • 倍增求第 kk 个 1:把 O(log⁡2n)O(\log^2 n) 降到 O(log⁡n)O(\log n),是树状数组的固定套路, 值得当作模板记住。

数据说明

  • 本题即洛谷 P2596「[ZJOI2006] 书架」/ BZOJ1861「Book 书架」,题面与数据范围 (n,m⩽8×104n, m \leqslant 8 \times 10^4、Insert 的 T∈{−1,0,1}T \in \{-1, 0, 1\})与原题一致。
  • 素材源的 std.cpp 用的是数组版 Splay(pos[] 把书号映射到节点,Insert 与中序前驱/后继 交换节点内保存的书号);本文的树状数组解法与之独立,两者在全部 10 组数据上输出一致, 可互为交叉验证。
  • 本目录的 data/ 由随题提供的生成脚本(data.py)自动生成,属于自造数据, 题面亦为按公开页面重建;因此出题意图与官方原题可能存在细节偏差, 但本解的所有结论均已在该 10 组数据上逐点验证通过。
  • 题面所给样例共 6 个输出,main.cpp 与 main.py 均逐一匹配; 额外用固定种子的随机小数据与 vector 暴力解做了对拍(C++ 累计 292 组、Python 累计 264 组, 覆盖 n=3n = 3 的最小规模、n=300n = 300 的中等规模与 Top/Bottom 反复重排), 另外还与素材源的 Splay 解做了 61 组三方交叉验证,全部一致。 还用 n=3n = 3、m=8×104m = 8 \times 10^4 的极端数据(几乎全是 Top/Bottom)验证了 “两端各留 mm 格”确实是紧的:左游标最低恰好降到坐标 55,仍在数组范围内, 且 C++ 与 Python 输出完全一致。

图示解析

下图重演题面样例。样例 n=m=10n = m = 10,取 base=m+5=15\text{base} = m + 5 = 15,初始第 ii 本书在坐标 15+i15 + i, 即 1→16,  3→17,  2→18,  7→19,  5→20,  8→21,  10→22,  4→23,  9→24,  6→251 \to 16,\; 3 \to 17,\; 2 \to 18,\; 7 \to 19,\; 5 \to 20,\; 8 \to 21,\; 10 \to 22,\; 4 \to 23,\; 9 \to 24,\; 6 \to 25。 命令流是 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 用右侧空位, 两者各至多移动 mm 次,因此预留在两端各 mm 格刚好不会撞车。第二,Ask S 是对 pos[S] 做一次 前缀和,Query S 是在同一个 BIT 上找第 SS 个 1,两个方向的查询共用一个结构—— 这正是选择树状数组的理由。第三,坐标轴上允许存在空位(如 15、17、20 后来都空了), 它们不影响正确性:Insert 只交换两本书的坐标标签,只要 pos / rev 保持一致、 c(⋅)c(\cdot) 集合不变即可。

样例里的 Insert 4 -1 跟踪下来恰好是:4 在坐标 23,它的排名是 prefix(23) = 8, 第 8−1=78 - 1 = 7 个 1 在坐标 22,于是 4 与坐标 22 上的书 10 互换。本例中 4 与它的前驱 坐标刚好相邻(23 与 22),所以写成 p - 1 也能对;但 Top / Bottom 在坐标轴上 挖出空位后,排名相邻的两本书坐标就会隔开。

这不是纸上推演,而是实测过的:把 main.py 里那行换成 q = p + t(“坐标直接加 TT”), 在本题 10 组数据中有 5 组输出错误(problem4 / 5 / 6 / 7 / 9); 唯一能蒙对的大数据点 problem10 恰好因为它的 7680076800 条 Insert 配了 00 条 Top / Bottom, 坐标轴上从未出现空位。所以“先 prefix 定出排名,再取第 k+Tk + T 个 1”不是可选优化, 而是本写法必须踩准的一步。

上面这条坐标轨迹是用真实程序逐行回放核对的(坐标 22 上的书确实是 10),不是纸上推演。