LOJ 6515《贪玩蓝月》这题，光看名字还以为又是哪个网页游戏的推广题，点进去才发现是一个相当典型的“数据结构套背包”模型。题目让你维护一个双端队列，队列里每个物品有重量 w 和价值 v，你需要在队首、队尾任意加东西、删东西，然后随时回答：在当前队列中选一些物品，容量不超过 c 的时候，最大总价值是多少。说白了，就是一个支持双端插入删除的 01 背包查询。这题我第一次见的时候，第一反应是用线段树分治离线做，后来发现有更漂亮的双栈在线做法，思路简单、常数小、还很好写，特别适合拿来练手。

1. 题意与核心难点

1.1 题目实质拆解

把操作抽象一下，队列中的每个元素就是一个“物品”，物品有两个属性：

• w：重量，或者叫体积；
• v：价值，或者叫魅力值。

操作分四种：

• 在队首插入一个物品；
• 在队尾插入一个物品；
• 从队首弹出一个物品；
• 从队尾弹出一个物品。

每次询问给一个容量上限 c，要求从当前队列中选若干物品，让总重量不超过 c，并且总价值最大。注意是“当前队列”，也就是说每次插入和删除都会影响后续查询的答案。

这题的难点不在于背包本身，而在于“删除”。普通的 01 背包，我们只会往 DP 数组里加物品，不会删物品。加物品很容易，因为转移是向下的：从旧状态推出新状态。可一旦要删掉某个物品，问题就麻烦了，你不能简单地把这次转移“逆运算”回去，因为同一个 DP 值可能是多种物品组合得到的，删除一个物品后，你根本不知道哪些状态是依赖它更新出来的。

1.2 为什么不能直接做可撤销背包

很多人第一反应是写一个“带撤销的背包”：每个物品入栈时记录它改动了哪些位置，撤销的时候再把这些位置恢复。对单个栈来说，这确实是可行的：push 时记录修改，pop 时回滚。但这里是双端队列，两端都能进出，靠一个栈根本模拟不了。

退一步讲，就算你用两个栈硬模拟，查询的时候还需要把两个栈里的物品合并。合并两个背包的朴素做法是枚举两侧各自选了多重，也就是 O(C^2)。如果 C 是几百、操作是几万次，O(操作数 * C^2) 直接超时。

所以核心就变成了两个问题：

1. 怎么让“双端队列”的插入删除变得可维护；
2. 怎么让“合并两个背包”的代价降下来。

双栈模型恰好能同时解决这两个问题。

2. 用两个栈还原双端队列

2.1 栈顶朝外的双栈设计

栈和队列最大的区别是：栈只能在一端进出，队列是两端进出。一个栈没法模拟队列，但两个栈可以。经典的队列用两个栈实现是“一个负责进、一个负责出”，查询时只用到两个栈的 DP 值，不需要真的把队首队尾连起来。

对于双端队列，我习惯这样的设计：

• 左栈 L：栈顶代表队首方向；
• 右栈 R：栈顶代表队尾方向。

示意图可以理解为：

队首方向 队尾方向 L顶 → L底 R底 → R顶

左右两个栈的栈底靠在一起。这样：

• push_front：直接压入 L，新元素变成新的队首；
• push_back：直接压入 R，新元素变成新的队尾；
• pop_front：弹 L 的栈顶；
• pop_back：弹 R 的栈顶。

这个设计下，两个栈的栈顶都朝队列外面，栈底都朝中间，所以任意一端插入弹出都只影响对应栈的栈顶，天然支持 O(1) 的单次栈操作。

2.2 翻倒操作与摊还代价

但是问题来了：如果 pop_front 的时候 L 是空的，而 R 里有元素，队首其实在 R 的栈底方向，这时候你没法直接弹 R 的栈底。解决办法是把 R 里的元素全部倒进 L。

R 的栈顶是队尾方向，从 R 弹出元素的顺序是：队尾、倒数第二个、……、队首。这些元素依次压入 L 之后，L 的栈顶恰好就是原来的队首。所以执行：

while (R非空) { L.push(R.top()); R.pop(); }

之后 L 从栈顶到栈底就是原来的队首到队尾，此时再 L.pop() 就可以删掉真正的队首了。

反过来，pop_back 时若 R 空，就把 L 全部倒进 R，操作是对称的。

这个翻倒过程看起来每次都要搬一大堆元素，会不会总复杂度爆炸？不会，这就是经典的摊还分析。任何一个元素从 R 倒进 L 之后，它要么在 L 里被弹出，要么下次再被倒回 R。一个元素每次“倒”都会换一个栈，而每个栈在被倒空之前，另一侧必为空。实际上每个元素在整个生命周期里只会被翻倒常数次，总翻倒次数是 O(n) 级别的。

要注意的是：我们这里每个“栈顶元素”本身就是一件物品，而每个物品进出栈时都要更新对应栈的背包 DP，所以翻倒的代价不是 O(1)，而是 O(C)，因为每搬一次物品就要用它做一次背包转移。这一点的摊还分析在后面会一起算。

3. 栈内背包 DP 的维护

3.1 增量式更新：push 时顺带做转移

两个栈各自维护一个 DP 数组。以左栈 L 为例，假设 L 当前有 k 个元素，我用f_L[i][j]表示：考虑 L 的栈底到当前第 i 个元素（也就是 L 里任意 i 个元素的组合）中，重量恰好为 j 时能得到的最大价值。

你可能觉得栈底到栈顶的顺序会影响 DP 结果，其实不会。背包问题只关心“哪些物品可用”，不关心物品的先后顺序。所以每次 push 新物品时，只需要在旧 DP 数组的基础上，用这个新物品做一次 01 背包转移：

array<int, MAXC> cur = pre; // 不选新物品的情况 for (int j = 0; j + w <= C; ++j) { if (pre[j] != NEG) { cur[j + w] = max(cur[j + w], pre[j] + v); } }

注意这里一定用的是pre[j]，不是cur[j]。因为 pre 表示“加入这个物品之前”的状态。如果误用 cur[j]，同一个物品就会被重复取多次，变成完全背包了。

每次 push 之后，把这个 cur 存到历史数组里。这样 pop 的时候只需要丢掉历史数组的最后一层，就自动回到了加入上一个物品之前的状态，这就是可撤销的关键。

3.2 查询时如何合并两个栈

查询容量不超过 c 时，左栈贡献一部分重量 i，右栈贡献剩余重量 j，总重量 i + j 不超过 c。如果直接枚举 i 和 j，复杂度是 O(C^2)。但我们可以先处理右栈的“前缀最大值”：

pref[0] = B[0]; for (int j = 1; j <= c; ++j) { pref[j] = max(pref[j - 1], B[j]); }

pref[j] 表示右栈中选出总重量不超过 j 时的最大价值。然后枚举左栈重量 i：

for (int i = 0; i <= c; ++i) { if (A[i] != NEG) { ans = max(ans, A[i] + pref[c - i]); } }

这样查询就是 O(C) 的。如果题目要求“重量恰好为 c”，那就更简单，直接把 pref 换成 B 本身：

for (int i = 0; i <= c; ++i) { if (A[i] != NEG && B[c - i] != NEG) { ans = max(ans, A[i] + B[c - i]); } }

还有一个常见优化：查询时先判断两个栈哪个元素更少，枚举元素多的那边做前缀最大值、元素少的这边直接枚举重量，常数会更小一点。不过复杂度不变，仍然是 O(C)。

4. 完整实现与复杂度分析

4.1 核心代码实现

我习惯把栈和背包封装成一个结构体，这样逻辑清楚，不容易写乱。下面这份代码是“容量不超过 c”的版本，如果题目要求恰好容量，把 query 函数里的前缀最大值部分换成直接合并即可。

#include <bits/stdc++.h> using namespace std; const int MAXC = 505; // 容量上限，按题目调整 const int NEG = -1e9; // 不可达状态 struct Item { int w, v; }; struct StackDP { vector<Item> ele; // 栈内元素 vector<array<int, MAXC>> dp; // dp[i][0..C]: 前 i 个元素的背包 StackDP() { array<int, MAXC> a; a.fill(NEG); a[0] = 0; dp.push_back(a); // 空栈：只有重量 0 可达 } int sz() const { return (int)ele.size(); } void push(const Item& x) { const array<int, MAXC>& pre = dp.back(); array<int, MAXC> cur = pre; // 不选 x for (int j = 0; j + x.w < MAXC; ++j) { if (pre[j] != NEG) { cur[j + x.w] = max(cur[j + x.w], pre[j] + x.v); } } ele.push_back(x); dp.push_back(cur); } void pop() { ele.pop_back(); dp.pop_back(); // 直接回退历史 } }; struct DequeDP { StackDP L, R; // L顶=队首，R顶=队尾 void push_front(const Item& x) { L.push(x); } void push_back(const Item& x) { R.push(x); } void pop_front() { if (L.sz() == 0) { while (R.sz() > 0) { Item x = R.ele.back(); R.pop(); L.push(x); } } L.pop(); } void pop_back() { if (R.sz() == 0) { while (L.sz() > 0) { Item x = L.ele.back(); L.pop(); R.push(x); } } R.pop(); } int query(int cap) { const auto& A = L.dp.back(); const auto& B = R.dp.back(); // 对右栈做前缀最大值 vector<int> pref(cap + 1, NEG); int curBest = NEG; for (int j = 0; j <= cap; ++j) { curBest = max(curBest, B[j]); pref[j] = curBest; } int ans = NEG; for (int i = 0; i <= cap; ++i) { if (A[i] != NEG) { ans = max(ans, A[i] + pref[cap - i]); } } return ans; } };

这里唯一要注意的是翻倒的时候，我直接访问了R.ele.back()，然后立刻R.pop()，再L.push(x)。因为 R 的 pop 会丢掉 R 里最后一个元素的背包历史，而 L 的 push 会把同一个元素加到自己的背包历史里。这个顺序不能反：先取出元素，再弹栈，再压入另一个栈。

pop_front和pop_back的翻倒逻辑都是“目标栈为空时，把另一个栈全部倒过来”。倒完之后，目标栈的栈顶恰好就是要弹出的队首（或队尾），所以最后直接pop()就可以。

4.2 复杂度到底是多少

先看单次操作：

• push_front / push_back：O(C)，因为要基于旧 DP 做一次背包转移；
• pop_front / pop_back：O(C)，因为要弹出 dp 历史数组的最后一层，数组本身的弹出是 O(1)，但如果有翻倒，每个被搬运的元素都会触发一次 push，也就是 O(C)；
• query：O(C)。

看起来每个操作都是 O(C)，但翻倒会把一次 pop 的代价放大到 O(元素个数 * C)。好在摊还下来，每个元素最多被搬运常数次。为什么？

考虑一个元素从 R 被搬到 L，搬完之后 R 为空。之后这个元素想再被搬一次，必须等到 L 为空、R 里有新的元素并且又需要被搬到 L。也就是说，每次大规模翻倒都会把一侧清空。元素在两侧之间切换的次数是有限的，本质上每个元素只会经历“入场 → 可能被翻倒 → 出场”这个过程。总时间复杂度是 O((操作次数 + 翻倒搬运次数) * C)，也就是 O(qC)。

对比一下朴素做法：如果每次查询都暴力合并两个栈，一次查询就是 O(C^2)。双栈做法把查询降到了 O(C)，把插入删除也控制在 O(C) 级别，整体性能是质变。

5. 实战中的坑与排查技巧

5.1 初始化与负无穷

dp[0][0] 必须初始化为 0，其他位置为负无穷。这样才能表示“空栈只能组合出重量 0”。如果你把 dp[0][0] 也设成负无穷，查询时所有状态都不可达，答案永远是负无穷。

负无穷的取值不要用-0x3f3f3f3f再加一个正数，因为价值累加之后可能溢出。直接用-1e9比较稳，如果价值范围很大，可以考虑-4e18，但记得用 long long 存。

5.2 翻倒是最大事故现场

翻倒最容易出 bug 的地方是方向。我一开始写的时候想当然地循环while (R.sz()) L.push(R.top())，但没有先取出元素就R.pop()，逻辑上没问题，可代码写成了：

while (R.sz() > 0) { R.pop(); L.push(???); }

结果不知道从哪取元素，直接 RE。正确流程一定是：

Item x = R.ele.back(); R.pop(); L.push(x);

另外，翻倒前一定要判断目标栈是否为空。如果 L 非空你又从 R 倒过来，就会把原来属于队首方向的东西和队尾方向的东西混在一起，队列顺序就乱了。我在本地上测试随机数据，队列顺序乱了之后，查询答案经常无规律可循。

5.3 空间占用与常数优化

dp 历史数组是这道题内存的主要来源。每次 push 都会复制一整份容量数组，如果容量 C = 500，一个 array<int, 505> 大约是 2 KB。队列里最多同时存在的元素个数不会超过操作数 q，所以两个栈总共的内存大约是 O(qC)。

如果 q 是五万、C 是五百，内存不到 110 MB，在很多 OJ 上能过。但如果 q 是十万、C 再大一点，可能就有点紧张了。可以做的优化：

• 预估最大操作数，提前L.dp.reserve(q + 5)，避免 vector 扩容反复拷贝；
• 在 StackDP 里只保存 dp 历史，不需要保存两个完整数组；
• 如果查询是“恰好容量”，可以把容量数组长度压缩到 max(c) + 1，而不是 MAXC。

常数方面，array<int, MAXC>是连续内存，缓存很友好。查询时对右栈做前缀最大值的临时数组可以复用，不要每次 query 都重新分配 vector。我习惯在 DequeDP 里预分配一个全局的tmp[MAXC]，查询时直接使用。

6. 扩展：模数背包与离线分治思路

6.1 如果题目变成模 m 背包

有些双端队列背包题会把询问改成：给定 m 和 x，问选出若干物品后总重量对 m 取模等于 x 的最大价值。这时候 DP 数组长度就不再是容量上限，而是模数 m。转移变化也很简单：

cur[(j + w) % m] = max(cur[(j + w) % m], pre[j] + v);

查询时枚举左栈余数 i，右栈余数就是(x - i + m) % m，合并 O(m)。其他逻辑完全一样。因为模 m 的余数数量通常比真实容量上限小很多，这种变式反而更好写。

6.2 另一条路：线段树分治

如果不追求在线，也可以用线段树分治做。核心思路是：每个物品都有一个存活时间段，从插入时刻到删除时刻。把每个时间段看成一个区间，覆盖到线段树的若干节点上。然后 DFS 遍历线段树，进入节点时把这个节点上的物品全部加入背包，离开节点时回滚加进去的物品。因为每个物品会被放到 O(log q) 个节点上，加入背包一次是 O(C)，总复杂度 O(q log q * C)。

这个做法也很经典，而且不依赖双端队列的性质，很多“支持删除的背包题”都能用。但它的代价是必须离线，而且空间和时间常数比双栈做法大不少。如果题目允许离线，两种方法都能过；如果题目强制在线，双栈做法就是首选。

回到《贪玩蓝月》这题本身，我实际写完双栈做法后在本地用随机数据对拍过，也试过几种不同的翻倒写法，最后发现“栈顶朝外 + 空栈翻倒”这个模型是最不容易出错的。建议你拿到题之后，先把队列操作和背包维护分开想清楚，再动手写代码。这个套路理解透之后，以后遇到“可删除背包”“双端队列加背包”之类的变体，基本都能一眼看穿。