2023 年蓝桥杯国赛的“交易账本”赛后好几个人问我思路。这道题题面读起来绕尤其那个“撤销操作”一旦理解歪了实现起来就是灾难。我自己第一版代码就吃过亏当时把所有操作当成“时间轴上的一次性变化”来处理结果一遇到撤销查询答案全错。后来把模型理顺发现核心其实就一句话每笔交易只在登记时间和撤销时间之间有效把这种区间贡献用差分拆开就能把整个问题变成一个时间扫描。这篇文章不聊虚的直接讲清楚题面、建模、代码和赛场上真正容易丢分的边界细节。无论你是 C/C 组还是 Java/Python 组这套思路都是通用的。1. 题面还原三类操作、时间戳和“第 k 笔交易”的编号1.1 三类操作拆开看“交易账本”这题的核心是处理一本账本操作一共有三种登记交易格式为1 t id x含义是在时间点t账户id发生了一笔金额为x的变动。x 0表示入账收入x 0表示出账支出。查询余额格式为2 t id含义是在时间点t查询账户id的当前余额。撤销交易格式为3 t k含义是在时间点t把历史上输入的第k笔交易作废。作废之后这笔交易的金额不再影响撤销时间点之后的余额。输入会给你一个操作总数n然后依次给出n个操作。题目要你把每次查询操作的答案按输入顺序输出。注意一个容易混淆的细节这里的“第k笔交易”指的是按输入顺序编号的第k笔登记交易不是第k个操作。换句话说每个1操作天然有一个编号这个编号就是它出现的次序。撤销操作只会引用之前已经出现过的交易编号。1.2 最容易读歪的两个地方第一时间戳是操作自带的信息不代表输入顺序。输入给你一个时间t意思是这个操作发生在时间点t但输入顺序可能完全乱序。比如第一个读入的操作可能是1 100 1 10发生在时间 100第二个读入的操作可能是2 5 1查询时间 5。所以绝对不能认为“先读入的操作时间一定更早”。第二撤销之后的查询余额要立刻变回来。如果第 2 笔交易在时间 8 被撤销那么时间 9 的查询就看不到这第 2 笔交易了。但如果查询时间等于 7也就是撤销时间之前这笔交易依然有效。我带过一些同学复盘这道题发现大家最容易卡住的不是算法而是“撤销到底怎么作用于余额”。本质上是这样一个问题我们维护的不是一组固定的账目而是一堆“有生命周期”的账目。每笔交易的生命周期从登记时刻开始到撤销时刻结束没被撤销的交易生命周期就是无穷大。1.3 一个小样例把语义钉死看一个只有 6 个操作的例子6 1 2 1 10 2 5 1 3 7 1 2 8 1 1 3 2 20 2 10 2逐行解释第 1 行时间 2账户 1 入账 10。这笔交易编号为 1。第 2 行时间 5查询账户 1输出 10。第 3 行时间 7撤销第 1 笔交易。注意撤销操作发生的时间是 7意味着从时间 7 开始第 1 笔交易不再生效。第 4 行时间 8查询账户 1此时第 1 笔交易已被撤销输出 0。第 5 行时间 3账户 2 入账 20。这笔交易编号为 2虽然它在输入顺序上排第 5但它发生的时间是 3。第 6 行时间 10查询账户 2输出 20。所以样例输出是10 0 20这个例子虽然简单但它有两个关键点一是撤销之后余额立刻变回 0二是交易登记时间可以早于前面某些操作的输入时间处理时要按时间点排序不能按输入顺序。2. 暴力做法为什么不行从 O(NQ) 到平衡树的弯路2.1 朴素重算前缀和最容易想到的做法是维护一个数组记录每个账户当前余额然后遇到查询直接遍历所有历史交易把时间点小于等于查询时间、且没被撤销的交易全部累加。这样的复杂度是 O(查询次数 × 历史交易数)最坏情况 O(NQ)当 N 到 10^5、10^6 级别时直接超时。还有一个更隐蔽的问题即使你每来一笔交易就把账户余额实时更新撤销操作依然不好处理。撤销的是一笔历史交易如果直接“当前余额减掉这笔交易”只能修正当下的余额修正不了这个撤销对过去查询的影响也回答不了“某个历史时刻的余额”。因为查询可以发生在任意时间点你可以随时问“时间 100 时账户 5 余额是多少”而那时候这笔交易可能还没被撤销。2.2 为什么平衡树/动态前缀和也不是好方案有些选手会想既然要支持删除历史交易并且要按时间查前缀余额那我可以对每个账户维护一棵平衡树节点是交易时间值是金额查询时求前缀和。理论上可行但实现代价太大了。这里有个很容易被忽略的点一笔交易被撤销之后它影响的是从登记时间到撤销时间这个区间而不是某个单独的时间点。撤销不是简单地删掉一个点而是让这个点的贡献“在某个时间之后归零”。如果硬要用平衡树维护你会在撤销时要修改这个交易对所有未来查询的影响这等于做一次区间修改而不是点删除平衡树写起来极其痛苦。另一个常见弯路是线段树动态开点按时间轴建线段树每笔交易在登记时间点加金额撤销时在撤销时间点减金额。等等这不就是正确解法吗方向其实对了但如果用线段树做还要维护每个账户的树代码量很大。而事实上这个问题根本不需要在线处理离线排序 差分数组才是最匹配的武器。2.3 先想清楚“不变的量”再动手暴力方案的问题在于它把每笔交易看成“一个发生即永久生效”的静态点导致撤销时只能做局部修正。但如果我们换个视角把每笔交易看作一个“从登记时间开始、到撤销时间为止的区间”那么整个问题就变成了在时间轴上有很多区间每个区间有一个权值查询某个时间点时累加所有覆盖该时间点的区间权值。这个模型有一个非常漂亮的性质区间加、点查询天生适合差分。3. 核心建模把永久账目变成有限区间再用差分消掉撤销3.1 一维差分复习余额就是时间轴上的前缀和先复习一个最基础的工具。假设有一笔交易金额是x发生在时间t且永远不会被撤销。那么它对余额的贡献是在t时刻之后的所有查询都要加上x。这等价于在时间轴的t位置放一个增量x然后做前缀和。如果有多笔交易每个账户的余额就是该账户所有“时间增量”的前缀和。举个例子账户 1 在时间 2 入账 10在时间 5 出账 3那么时间 1 时余额 0时间 3 时余额 10时间 6 时余额 7。这本质上就是时间轴 1 2 3 4 5 6 变化量 10 -3 前缀和 0 10 10 10 7 7余额永远等于“从时间轴 0 到当前时间的所有变化量之和”。注意这里的位置是时间点不是数组下标。3.2 撤销的本质截断生命周期现在加入撤销。第k笔交易如果没被撤销它的贡献区间是[登记时间, ∞)如果被撤销了贡献区间是[登记时间, 撤销时间)。关键来了一个区间[l, r)内的恒定贡献x可以用差分表示为在l处加x在r处加-x也就是说一笔原本“永远生效”的交易被撤销后只是在生命周期结束时补上一个相反数把之前的贡献抵消掉。这就像你追了一部连载小说从第 1 章开始订阅到第 30 章停更你的订阅行为只在第 1 章到第 30 章之间有影响第 31 章开始就没有了。3.3 事件化每笔交易拆成最多两个“余额变化点”基于这个模型我们可以把所有操作换一种形式来表达每笔登记交易(t, id, x)如果没被撤销生成一个事件(t, id, x)。如果被撤销且撤销时间revT大于登记时间t生成两个事件(t, id, x)和(revT, id, -x)。每个查询操作生成一个查询事件(T, id)答案就是扫描到当前时间点时账户id的累计余额。把所有事件按时间点排序按顺序扫描。遇到x、-x就更新对应账户的当前余额遇到查询就把当前余额记录到答案数组里。这样我们完全不需要动态删除也不需要对每个历史时刻重新计算一遍扫描就拿到了所有查询的答案。4. 代码实现两遍读入、事件排序、按账户扫描4.1 数据结构与读入策略核心数据结构有三个struct Tx { long long addT; // 登记时间 int acct; // 账户 id long long amt; // 金额 bool revoked; // 是否被撤销 long long revT; // 撤销时间 }; struct Event { long long t; // 事件时间 int acct; // 账户 id long long delta; // 余额变化量查询事件该值为 0 int type; // 0 表示余额变化1 表示查询 };读入策略有个细节要提前想清楚撤销操作引用的是第k笔交易而第k笔交易一定在撤销操作之前读入。所以我在读入阶段可以实时标记撤销for (int i 1; i n; i) { int op; cin op; if (op 1) { long long t; int id; long long x; cin t id x; tx.push_back({t, id, x, false, 0}); } else if (op 2) { long long t; int id; cin t id; events.push_back({t, id, 0, 1}); } else { long long t; int k; cin t k; tx[k].revoked true; tx[k].revT t; } }注意如果题目没有保证每笔交易“只能被撤销一次”那么重复撤销时不应该覆盖第一次的撤销时间。稳妥写法是加一个判断只有!tx[k].revoked时才更新。这个我在后面边界章节再展开。4.2 构建事件的核心代码读完所有操作后每笔交易的撤销状态已经确定。接下来遍历所有交易把它们转换成一到两个事件for (int i 1; i (int)tx.size(); i) { if (!tx[i].revoked) { events.push_back({tx[i].addT, tx[i].acct, tx[i].amt, 0}); } else if (tx[i].revT tx[i].addT) { // 正常有效区间 [addT, revT) events.push_back({tx[i].addT, tx[i].acct, tx[i].amt, 0}); events.push_back({tx[i].revT, tx[i].acct, -tx[i].amt, 0}); } // 如果 revT addT说明这笔交易从未生效直接忽略 }这里有个关键判断revT addT才生成两个事件。虽然正常数据不会出现撤销时间早于登记时间但加上这个防御逻辑能保证即使遇到奇怪的用例也不出错。如果撤销时间和登记时间相同这笔交易瞬间登记又瞬间被撤销那它压根不应该贡献任何余额所以两个事件都不生成。4.3 排序与扫描附 C 完整代码事件排序的规则要非常小心同一时间点上余额变化事件必须先于查询事件处理。换句话说如果时间t有一笔入账同时有一个查询时间也是t按题意这个查询应该能看到这笔入账的结果。排序规则sort(events.begin(), events.end(), [](const Event a, const Event b) { if (a.t ! b.t) return a.t b.t; return a.type b.type; // 修改(0)在前查询(1)在后 });账户 id 可能非常大也可能出现负数账户一般题目给的是正数 id但为了保险我用离散化处理把所有出现的账户 id 收集起来排序去重映射到数组下标。完整可运行的 C 代码#include bits/stdc.h using namespace std; using ll long long; struct Tx { ll addT; int acct; ll amt; bool revoked; ll revT; }; struct Event { ll t; int acct; ll delta; int type; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorTx tx(1); // 下标从 1 开始 vectorEvent events; vectorint allAcct; // 用于离散化 vectorll ans; for (int i 1; i n; i) { int op; cin op; if (op 1) { ll t; int id; ll x; cin t id x; tx.push_back({t, id, x, false, 0}); allAcct.push_back(id); } else if (op 2) { ll t; int id; cin t id; events.push_back({t, id, 0, 1}); allAcct.push_back(id); } else { ll t; int k; cin t k; if (!tx[k].revoked) { tx[k].revoked true; tx[k].revT t; } } } // 构建余额变化事件 for (int i 1; i (int)tx.size(); i) { if (!tx[i].revoked) { events.push_back({tx[i].addT, tx[i].acct, tx[i].amt, 0}); } else if (tx[i].revT tx[i].addT) { events.push_back({tx[i].addT, tx[i].acct, tx[i].amt, 0}); events.push_back({tx[i].revT, tx[i].acct, -tx[i].amt, 0}); } } // 离散化账户 sort(allAcct.begin(), allAcct.end()); allAcct.erase(unique(allAcct.begin(), allAcct.end()), allAcct.end()); // 排序同一时间先处理余额变化再处理查询 sort(events.begin(), events.end(), [](const Event a, const Event b) { if (a.t ! b.t) return a.t b.t; return a.type b.type; }); vectorll bal(allAcct.size(), 0); auto getIndex [](int acct) { return lower_bound(allAcct.begin(), allAcct.end(), acct) - allAcct.begin(); }; for (const auto e : events) { int idx getIndex(e.acct); if (e.type 0) { bal[idx] e.delta; } else { ans.push_back(bal[idx]); } } for (ll v : ans) { cout v \n; } return 0; }用前面那个 6 行样例跑一遍逻辑交易 1登记时间 2账户 1金额 10撤销时间 7。生成事件(2, 1, 10)、(7, 1, -10)。交易 2登记时间 3账户 2金额 20未撤销。生成事件(3, 2, 20)。查询事件(5, 1)、(8, 1)、(10, 2)。按时间排序后的扫描过程t2 : bal[1] 10 - bal[1] 10 t3 : bal[2] 20 - bal[2] 20 t5 : query(1) - ans: 10 t7 : bal[1] -10 - bal[1] 0 t8 : query(1) - ans: 0 t10 : query(2) - ans: 20输出结果和之前手动推导完全一致。4.4 Python 版本参考蓝桥杯很多同学用 Python 交题这里给一个等价的 Python 实现。Python 的defaultdict可以直接当离散化哈希表用代码更短import sys from collections import defaultdict def solve(): input sys.stdin.readline n int(input()) tx [None] # 1-based events [] ans [] for i in range(1, n 1): op list(map(int, input().split())) if op[0] 1: _, t, acct, x op tx.append([t, acct, x, False, 0]) elif op[0] 2: _, t, acct op events.append((t, acct, 0, 1)) else: _, t, k op if not tx[k][3]: tx[k][3] True tx[k][4] t for i in range(1, len(tx)): t, acct, x, revoked, revT tx[i] if not revoked: events.append((t, acct, x, 0)) elif revT t: events.append((t, acct, x, 0)) events.append((revT, acct, -x, 0)) # 同一时间修改(0)排在查询(1)之前 events.sort(keylambda e: (e[0], e[3])) bal defaultdict(int) for t, acct, delta, typ in events: if typ 0: bal[acct] delta else: ans.append(bal[acct]) sys.stdout.write(\n.join(map(str, ans)) \n) if __name__ __main__: solve()性能上Python 版本的defaultdict哈希访问在 10^5 级别完全够用如果数据量到 10^6建议转为 C 或把账户离散化成数组。5. 同一时刻的事件顺序和边界条件最容易白丢分的地方5.1 修改事件必须先于查询事件这是最容易被忽略、又最致命的一点。假设一笔交易登记时间是t 5另一个查询时间也是t 5那么查询能否看到这笔交易按常见题面语义交易在时间 5 发生查询在时间 5 进行应该能看到。所以扫描同一时间点时必须先把所有余额变化处理完再回答查询。反过来如果一笔交易在t 5被撤销另一个查询时间也是t 5那么查询不应该看到这笔交易。因为撤销事件生成的-x在时间 5 执行先执行了-x再查询结果自然是不包含。这两个规则用同一条排序逻辑就都满足了type0 的修改事件排在 type1 的查询事件之前。如果你不放心题目是否保证同一时间点只有一个操作可以自己在心里强化一下这个约定。按这个约定写是所有标准题解都认可的。5.2 没被撤销的交易、重复撤销、非法撤销没被撤销的交易不会生成右端点事件所以它的贡献从登记时间一直延续到扫描结束。这里要注意事件扫描是从小时间到大时间如果一个没被撤销的交易登记时间很大比如是 10^18它依然会生成一个时间点为 10^18 的事件排序后照样能处理。除非你用了固定大小的数组去存时间轴否则不要用“时间轴数组”的做法一定要用事件排序的方式。重复撤销的情况题目一般会保证不会出现但防御性代码成本很低我在读入撤销操作时判断!tx[k].revoked才更新。这样即使出现“重复撤销同一笔交易”也只按第一次撤销时间算。如果题目要求的是“重复撤销不合法”那这种处理也不会影响正确数据。非法撤销指撤销一个不存在的交易编号比如k0或者k 当前交易数正常数据不会有但如果你在数组下标上直接访问至少保证tx初始有一个占位元素下标从 1 开始。这样即使k0也不会越界只是会错误地标记占位元素正常数据不会触发。5.3 时间戳与编号的精度问题时间点t和金额x都可能超过int范围。金额可能是负数可能达到 10^9 级别累加多个账户余额后可能超过 2^31。所以 C 里所有时间、金额、余额都要用long long。Python 不需要担心这个但 C 选手很容易在这里栽跟头。另外还有一个隐蔽的点撤销事件生成的减量是-tx[i].amt。如果tx[i].amt本身是负数比如一笔出账金额是 -5那么它生效时事件是-5撤销时事件是5。千万不要写成abs或者其他变换直接取相反数就行。这个逻辑对正负金额都成立。6. 举一反三从“交易账本”看一类可离线的区间题目6.1 变体一查询一段时间的累计变动如果把查询从“单点余额”改成“查询 [L, R] 时间区间内账户 id 的总变动”怎么做同样利用差分统计出所有余额变化事件的前缀和数组pref区间和就是pref[R] - pref[L-1]。但因为账户很多不能再维护一个简单数组需要把每个账户单独排序处理或者用树状数组离线做。思路的本质没变把操作变成事件离线扫描用差分把动态问题静态化。交易账本里我们只是查询单点所以用一个累计值和两个事件就解决了如果查询区间就再加一层前缀和相减。6.2 变体二强制在线的交易账本如果题目改成“在线强制”也就是不能先读完整份输入必须边读边回答那么差异分会失效因为你不知道一笔交易未来会不会被撤销。这种时候要上的数据结构是线段树分治或者可持久化线段树。比如用线段树分治把每笔交易的有效区间插入到线段树的节点上查询时沿路径累加贡献复杂度 O(N log^2 N) 左右。所以这道题能离线是一个很强的性质要主动利用。看到“最终答案要按输入顺序输出”“撤销引用历史编号”就应该意识到可以先把全部输入存下来再处理。6.3 赛场上识别“差分题”的三个信号我在赛后复盘时总结了一套判断方法碰到类似的题目可以快速产生思路操作带时间戳但查询是点查询优先想排序扫描。有删除/撤销/失效操作但只影响未来查询优先想“把生命周期转成区间”。数据规模在 10^5 甚至 10^6不允许嵌套遍历基本可以排除暴力。交易账本恰好三个信号全中。先想清楚“什么是不变的”再想“哪些操作能转化为事件”最后再动手写代码比直接开一个复杂数据结构稳得多。我自己的体会是这道题给我最大的收获不是差分这个技巧本身而是“撤销”这个动作可以用一个反向事件来建模。之后再做类似“括号匹配”“区间覆盖”“历史版本查询”的题我都会条件反射地问一句能不能把生命周期拆成左端点和右端点两个事件能就离正解不远了。