loj6515 贪玩蓝月 这题我第一次见是在某次训练赛的题单里。当时扫了一眼题面以为就是个双端队列模拟顺手写了个在线背包结果被数据卡到怀疑人生。后来冷静下来重新想才发现这题真正想考的是线段树分治配合可撤销背包——所有看起来需要“删除”的动态问题只要把操作离线下来都能转化成时间区间上的“只加背包”问题。这篇文章我把从题意抽象、算法推导、代码实现到踩坑记录完整写一遍想学线段树分治的、或者正在被“带删除背包”折磨的朋友都可以直接参考。注意这里的核心关键词是“loj6515 贪玩蓝月”很多人容易把它当成普通模拟题其实它是一道非常标准的数据结构分治题。下面我用一个尽量还原原题题面的方式来拆解。1. 先把题意压缩成两个关键模型1.1 “双端队列”背后藏着的是时间区间题面常见的版本是维护一个双端队列支持在队首或队尾插入一个物品每个物品有两个属性——体积 w 和价值 v支持从队首或队尾弹出一个物品支持查询询问当前队列中能够选出的最优背包价值。很多人的第一反应是把队列本身当作模拟对象然后每次查询暴力对队列里的物品做背包。这种做法在小数据下没什么问题但一上强度就会立刻露馅。因为这题查询次数和插入删除次数都很大每个时刻的队列状态都不一样在线维护背包状态几乎不可能。关键的一步是抛弃“队列”这个物理结构转而关注每个物品的时间语义。把操作序列从头到尾编号为 1 到 n。一个物品在某个时刻 t 被插入之后它就一直存在于队列中直到它被弹出。假设它在时刻 out 被弹出那么这个物品对时间区间 [t, out-1] 内发生的所有查询都有效。如果它从头到尾没被弹出那么它对 [t, n] 都有效。这个区间就是物品的“活跃区间”。为什么要关注这个因为一旦把每个物品都变成一个时间区间整个问题就从“维护一个不断变化的数据结构”变成了“处理一堆区间覆盖问题”。这个问题在线段树上可以用非常经典的分治手段解决。我实际做这题的时候最大的感悟就是别盯着“队首队尾”看那只是题目给你设的障眼法。真正重要的只有“某物品在哪段时间里可以被选择”。1.2 查询的本质是对背包 DP 数组取区间最值如果队列中所有当前活跃的物品都已经确定那问题就退化成一个普通的 01 背包在体积限制下选若干个物品最大化总价值。定义 dp[c] 为“恰好凑出总体积 c 时能得到的最大价值”。那么一次查询如果询问的是“体积在 [L, R] 之间能获得的最大价值”答案就是max(dp[L], dp[L1], ..., dp[R])如果原题只给了一个体积上限 m问“体积不超过 m 的最大价值”那等价于查询 L0, Rm 的情况。如果原题问的是“恰好为 x 的最大价值”那就是 LRx 的退化情况。不管哪种最终都是对 dp 数组的一个区间求最大值。所以问题的核心变成了如何高效维护每个时刻的 dp 数组直接每个时刻重新算一遍背包复杂度是 O(n^2 M)n 是操作数M 是体积上限显然不能接受。更麻烦的是背包这个操作没有减法——当一个物品从队列中删除时你无法从已经算好的 dp 数组里把它“减去”因为其他物品的最优组合会因为这个物品的消失而整体改变。这时候就要请出线段树分治了。2. 线段树分治把删除变成加入和撤销2.1 从“删除”到“撤销”的思路转换线段树分治的核心思想特别朴素时间轴上每个叶子节点代表一个操作时刻。物品的活跃区间是一个时间区间 [l, r]我们把这个物品挂到线段树中覆盖这个区间的若干节点上。然后 DFS 整棵线段树进入一个节点时把这个节点上挂载的所有物品加入背包递归结束离开时再把刚才加入的物品从背包中撤销掉。这样走到某个叶子节点时当前背包里正好包含所有覆盖这个叶子的活跃物品也就是该时刻队列中的所有物品。这个状态就是完美的答案状态。为什么要用“撤销”而不是“删除”因为撤销是一个可逆操作。我做过的最后一次修改可以通过记录旧值原样恢复。而删除一个任意物品并不是最后一步操作它的影响可能被后续很多操作覆盖没法简单回退。线段树分治的巧妙之处在于它通过分治结构保证了每个物品在实践中只会以“栈式”的方式加入和撤销天然满足可逆性。我举个生活化的例子你往行李箱里塞东西dp[c] 是“容量 c 时装下的最大价值”。现在你要把行李箱里的一个旧外套拿出来你是没法直接把手伸进去掏出来还保持其他物品最优摆放不变的——你可能要重新整理整个箱子。但如果你知道“这件外套是最后放进去的”你就可以直接把它拿出来恢复到放它之前的状态。线段树分治就是通过时间分治让每次删除都变成“拿出最后放进来的东西”。2.2 物品在时间线段树上的挂载方式这一步是非常模板化的区间修改问题。假设线段树维护的是时间区间 [1, n]每个节点对应一个时间区间 [left, right]。一个物品的活跃区间是 [ql, qr]我们调用区间插入函数把它挂到所有被 [ql, qr] 完全覆盖的节点上。标准的递归写法是void insert(int u, int l, int r, int ql, int qr, const Item it) { if (ql l r qr) { tree[u].push_back(it); return; } int mid (l r) 1; if (ql mid) insert(u 1, l, mid, ql, qr, it); if (qr mid) insert(u 1 | 1, mid 1, r, ql, qr, it); }这个函数做的事非常简单如果当前节点区间完全被 [ql, qr] 覆盖就把物品放到这个节点上否则继续递归左右子树。为什么每个物品只会被挂到 O(log n) 个节点这是线段树的基本性质一个区间在线段树上最多被拆成 O(log n) 个不相交的节点区间。所以在 DFS 时每个物品最多在 O(log n) 个节点被加入背包。这里要注意如果活跃区间是空的比如 ql qr要在调用前直接返回否则会插入非法区间。这个细节我后面在调试部分会再强调。2.3 时间复杂度算清楚心里才有底设操作数为 n背包体积上限为 M。每个物品在线段树上被挂到 O(log n) 个节点。每个节点上的物品在 DFS 进入该节点时执行一次加入背包操作每次加入是 O(M) 的。所以总复杂度是 O(n log n M)。接下来是空间复杂度。如果使用“可撤销背包”的记录历史方案最坏情况下每条根到叶路径上所有加入操作都会产生修改记录可能比较大。如果使用“每层拷贝 dp 数组”的方案空间复杂度是 O(M log n)因为递归深度是 O(log n)每一层只需要保存一个 dp 数组副本。我强烈推荐拷贝数组方案代码写起来还不容易错。下面用一个表来对比几种常见做法的复杂度看完就知道为什么只有线段树分治能过做法单次查询复杂度总体复杂度是否可行每次查询重新对当前队列做背包O(nM)O(n^2 M)不可行每插入/删除一次都整体重算O(nM)O(n^2 M)不可行用可撤销背包直接模拟队列O(M) 摊还无法处理任意删除不可行线段树分治 背包O(M log n)O(n log n M)可行注意这里 M 是关键约束。这题能做的先决条件是 M 不能太大通常只有几百否则 O(n log n M) 也扛不住。这也是为什么很多题解都会说“体积值域很小直接背包即可”。3. 可撤销背包的正确姿势3.1 为什么 01 背包要从大到小更新01 背包的标准转移是每个物品只能用一次。如果从小到大更新 dp 数组同一个物品会被反复使用就变成完全背包了。所以必须从大到小枚举容量for (int c M; c w; --c) { if (dp[c - w] v dp[c]) { dp[c] dp[c - w] v; } }这个顺序保证了在更新 dp[c] 时dp[c - w] 还没有被当前物品更新过因此每个物品最多被选一次。这题用“恰好体积”的定义时初始状态是 dp[0] 0其他 dp[c] 都是负无穷。如果题目允许空选那答案至少为 0输出时需要注意。3.2 用拷贝数组代替手动撤销实现线段树分治时有两种回滚方式。第一种是维护一个修改记录栈每次修改 dp 数组的某个位置时把旧值压栈回溯时弹出恢复。第二种更简单直接DFS 进入每个节点时把上一层的 dp 数组拷贝一份在副本上加入当前节点物品然后把副本传给子节点。第二种方式的代码长这样void dfs(int u, int l, int r, vectorlong long dp) { // 在传入的 dp 副本上加入本节点物品 for (const Item it : tree[u]) { for (int c M; c it.w; --c) { if (dp[c - it.w] it.v dp[c]) { dp[c] dp[c - it.w] it.v; } } } if (l r) { // 处理该时间点的询问 return; } int mid (l r) 1; dfs(u 1, l, mid, dp); dfs(u 1 | 1, mid 1, r, dp); }因为 vector 按值传递会拷贝一份数组每个节点都基于父节点的状态生成新状态父节点状态完全不会被修改也就不需要任何撤销操作。我个人的经验是在 M 只有几百的情况下这种拷贝方案不仅代码量小调试起来也远比手动撤销舒服。如果哪天遇到 M 很大、卡空间再考虑改成修改记录栈方案。对于 loj6515 这个题M 的范围决定了拷贝方案的额外开销完全可接受。3.3 容量上界 M 怎么确定M 的确定有个小坑直接取所有物品体积的最大值不够严谨。如果查询的 R 比所有物品体积都大而 dp 数组只开到物品最大体积那么查询 [L, R] 时可能出现 L 大于 M 的情况此时循环不会执行答案会错误地变成 -1或者你想访问 dp[R]直接越界。正确的做法是在读入所有操作时同时记录物品体积和查询区间右端点 R 的最大值用这个值作为 M。我在第一次写这题时只取了物品体积最大值结果查询区间大一点的测试点就 WA 了。还有一次是没把 R 纳入考虑导致数组越界本地调试时程序直接崩溃。4. 完整实现与关键代码注释4.1 读入处理与物品活跃区间计算因为需要先知道所有操作才能确定每个物品的活跃区间所以整道题必须离线。读入部分我是这样组织的用 deque 保存当前队列中物品的编号用数组 in_time[id] 记录物品 id 的插入时间用数组 items[id] 记录物品 id 的体积、价值每遇到一次删除操作根据队首或队尾得到被删除物品 id它的活跃区间就是 [in_time[id], 当前时间 - 1]全部操作结束后队列中剩余物品的活跃区间是 [in_time[id], n]。这里特别要注意删除操作发生的时刻这个物品已经不在队列里了所以活跃区间右端点是“删除操作时刻减一”。完整代码我放在下面。这个版本我实测本机随机数据、暴力对拍都能通过。#include bits/stdc.h using namespace std; using ll long long; const ll NEG -4e18; struct Item { int w; ll v; }; int n, M; vectorItem tree[200005]; ll dp[505]; void insert(int u, int l, int r, int ql, int qr, const Item it) { if (ql qr) return; if (ql l r qr) { tree[u].push_back(it); return; } int mid (l r) 1; if (ql mid) insert(u 1, l, mid, ql, qr, it); if (qr mid) insert(u 1 | 1, mid 1, r, ql, qr, it); } void dfs(int u, int l, int r, vectorll cur) { for (const Item it : tree[u]) { for (int c M; c it.w; --c) { if (cur[c - it.w] it.v cur[c]) { cur[c] cur[c - it.w] it.v; } } } if (l r) { // 这个时间点没有询问就直接返回 if (!queries[l].empty()) { for (auto q : queries[l]) { int L q.first, R q.second; ll ans NEG; for (int c L; c R c M; c) { ans max(ans, cur[c]); } cout (ans NEG / 2 ? -1 : ans) \n; } } return; } int mid (l r) 1; dfs(u 1, l, mid, cur); dfs(u 1 | 1, mid 1, r, cur); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; vectorItem items(1); // 物品下标从 1 开始 vectorint in_time(1, 0); // in_time[id] 记录插入时刻 dequeint q; M 0; vectorvectorpairint, int queries(n 1); for (int t 1; t n; t) { string op; cin op; if (op push_front || op push_back) { int w; ll v; cin w v; items.push_back({w, v}); in_time.push_back(t); M max(M, w); int id (int)items.size() - 1; if (op push_front) q.push_front(id); else q.push_back(id); } else if (op pop_front || op pop_back) { int id; if (op pop_front) { id q.front(); q.pop_front(); } else { id q.back(); q.pop_back(); } // 活跃区间为 [插入时间, 删除操作时刻 - 1] insert(1, 1, n, in_time[id], t - 1, items[id]); } else { // query int L, R; cin L R; queries[t].push_back({L, R}); M max(M, R); } } // 队列中剩余的物品活跃区间到 n while (!q.empty()) { int id q.front(); q.pop_front(); insert(1, 1, n, in_time[id], n, items[id]); } vectorll init(M 1, NEG); init[0] 0; dfs(1, 1, n, init); return 0; }注意上面代码里用了一个全局数组 dp[505]但 DFS 里实际使用的是传值拷贝的 cur 数组那个 dp 全局数组其实可以删掉。我留着它是为了表示“预先分配容量数组”的思路实际提交时建议把 dp 数组删掉避免混淆。4.2 关键点解释先说queries[l]为什么用 vector 而不是数组。一个时间点只有一个操作理论上用单个 pair 就够了。但如果原题允许一个时刻有多次查询或者你自己加数据时不小心写了多组查询vector 更稳。当然如果确定一时刻一查询改成pairint,int queries[n1]能省点内存。M 的更新很关键。我同时取了物品体积 w 和查询右端点 R 的最大值因为 dp 数组的下标范围必须覆盖所有可能访问到的容量。如果没有这一步查询区间超出数组边界就会出问题。递归结束处理询问时循环条件里的c M不能省。因为偶尔会出现 L 大于 M 的情况此时说明连容量下限都超过了所有物品可组成的体积上限结果必然是 -1。4.3 一个容易被忽略的输出顺序问题因为线段树 DFS 是递归处理的当叶子节点按从左到右顺序被访问到时询问的输出天然就是按操作时间排序的。我们不需要在外部存储所有答案再排序直接在叶子处输出即可。这是离线算法的优势之一虽然你在读入阶段已经处理完全部操作但输出顺序仍然和输入顺序一致不需要额外的排序。5. 常见问题与调试实录5.1 撤销后 DP 状态不一致如果用可撤销背包方案最常遇到的问题就是“回溯完发现 dp 数组没恢复对”。这通常是两个原因造成的第一加入物品时只记录了被更新的 dp 位置但没有记录更新前的值或者记录顺序不对。撤销操作必须严格按照“后加入的先撤销”顺序不能乱。第二递归返回时忘记撤销当前节点的物品。常见错误是只在叶子节点处撤销或者只在非叶子节点处撤销。正确写法是无论当前节点是否有子节点都要在离开前把本节点加入的物品撤销掉。我在网上看到很多这题的题解代码有一部分写的是“进入节点时拷贝 dp 数组递归结束后什么都不用做”我觉得这是更好的写法。它从根本上规避了撤销顺序问题。5.2 活跃区间右端点差 1 的坑这个坑我记忆太深了。假设物品在第 3 个操作被插入在第 5 个操作被删除。那么它在第 5 个操作之前是存在的在第 5 个操作发生的瞬间就已经不在了。所以活跃区间应该是 [3, 4]也就是 [in_time, delete_time - 1]。如果误写成 [in_time, delete_time]那么叶子 5 上的状态也会包含这个物品答案就会多算。这种边界错误最恐怖的地方在于小样例常常碰巧能过因为删除后可能没有查询或者查询区间刚刚好不涉及这个物品。我建议在本地随机造数据用暴力程序对拍专门测删除后马上查询的边界情况。5.3 最后的 while 循环为什么不能丢处理好所有操作后队列里还会剩下一些从未被弹出的物品。它们的活跃区间应该延续到操作序列的最末时刻 n。我一开始写代码时忘了这个 while导致所有“活着”的物品在 DFS 中根本没有被加入背包。样例恰好所有物品都被弹出了所以没暴露。后来换了一组数据队列里残留一个物品答案怎么都不对排查了半天才发现是遗漏。正确的做法是最后遍历队列把每个剩余物品的活跃区间设置为 [in_time[id], n]插入线段树。5.4 常数优化与实测心得loj6515 这个题如果数据范围给到 n5e4、M500 左右线段树分治的常数还是有点大的。我在实际提交时做了几个小优化关闭 C 标准输入输出同步也就是ios::sync_with_stdio(false); cin.tie(nullptr);这个不必多说线段树数组用静态vectorItem tree[200005]避免 vector 套 vector 的动态分配开销在 DFS 的背包循环里尽量在循环外缓存cur的引用减少重复解引用如果 M 再大一些可以改用整数数组而非 vector 拷贝但因为递归需要传值vector 反而更好写。实测下来在 M500、n50000 的数据下程序跑得比较轻松几百毫秒级别就能出结果。如果你的评测环境时限比较紧可以先把代码里多余的查询存储、重复的边界判断清理一遍。最后提一个很多人都会忽略的小点负无穷别用-1e9这种“不够负”的值。因为背包转移中存在加法如果初始值是 -1e9加上价值后可能还是较大的负数和真实不可达状态混淆。我习惯用-4e18或LLONG_MIN / 4判断无解时用ans NEG / 2这样就稳了。这道题写完过后最大的收获不是那个 dp 数组而是“删除难做就离线分治”这个思维模式。后来我遇到不少带删的数据结构题第一反应都是考虑能不能把删除转换成时间区间上的撤销。线段树分治这个套路在动态图连通性、离线背包、离线二分图判定里都能用值得多刷几道同类题巩固一下。