题目大意

有 $n$ 种玩偶，每种有价钱 $a_i$、价值 $b_i$ 和限购次数 $c_i$。
给定 $q$ 次询问，每次询问：

• 删除一个玩偶 $d_i$
• 背包容量变为 $e_i$
• 求此时多重背包的最大价值

不同询问相互独立，即每次删除只针对当前询问。

问题分析

1. 直接方法的瓶颈

如果对每个询问重新计算多重背包：

• 单次多重背包：$O(m \cdot \sum c_i)$ 或优化后 $O(n \cdot m)$
• $q$ 次询问：$O(q \cdot n \cdot m)$
• 数据范围：$n \leq 1000$，$m \leq 1000$，$q \leq 3\times 10^5$
• 直接计算不可行（约 $3\times 10^{11}$ 操作）

核心思路：前后缀分解

1. 前后缀背包预处理

定义：

• f_pre[i][j]：只使用前 $i$ 个物品（编号 $0$ 到 $i-1$），容量为 $j$ 的最大价值
• f_suf[i][j]：只使用后 $n-i$ 个物品（编号 $i$ 到 $n-1$），容量为 $j$ 的最大价值

这样预处理后，对于删除物品 $del$ 的询问：

• 可用物品 = 前 $del$ 个物品 + 后 $n-del-1$ 个物品
• 答案 = $\max\limits_{0 \leq k \leq money} \{ f\_pre[del][k] + f\_suf[del+1][money-k] \}$

2. 多重背包优化

使用 单调队列优化 的多重背包：

• 对每个余数 $r$（$0 \leq r < a_i$）分别处理
• 维护一个单调队列，保证队首是当前窗口的最大值
• 复杂度从 $O(m \cdot \sum c_i)$ 优化到 $O(n \cdot m)$

算法步骤

阶段 1：预处理前缀背包

1. 初始化 f_pre[0][j] = 0
2. 对于 $i = 1$ 到 $n$：
   • 先复制上一行的结果：f_pre[i] = f_pre[i-1]
   • 对当前物品进行单调队列优化的多重背包更新

阶段 2：预处理后缀背包

1. 初始化 f_suf[n+1][j] = 0
2. 对于 $i = n$ 到 $1$：
   • 先复制下一行的结果：f_suf[i] = f_suf[i+1]
   • 对当前物品进行单调队列优化的多重背包更新

阶段 3：处理询问

对于每个询问 $(del, money)$：

• 答案 = $\max\limits_{k=0}^{money} f\_pre[del][k] + f\_suf[del+2][money-k]$
• 注意下标调整：删除第 $del$ 个物品（0-indexed）后，前 $del$ 个物品对应 f_pre[del]，后 $n-del-1$ 个物品对应 f_suf[del+2]

复杂度分析

• 预处理：

  • 前缀背包：$O(n \cdot m)$
  • 后缀背包：$O(n \cdot m)$
  • 总计：$O(n \cdot m)$

• 回答询问：

  • 每个询问：$O(m)$（枚举容量分割）
  • 总计：$O(q \cdot m)$

• 总复杂度：$O((n + q) \cdot m)$

  • 最坏：$(1000 + 300000) \times 1000 \approx 3\times 10^8$，可以接受

关键点

1. 单调队列优化多重背包

对于物品 $(a, b, c)$：

• 按余数 $r$ 分组处理
• 维护队列存容量下标，保证 $f[j] - \frac{j}{a} \cdot b$ 单调递减
• 窗口大小：$c \cdot a$

2. 前后缀思想

• 将"删除一个元素"转化为"合并两个不包含该元素的背包"
• 避免重复计算，实现询问间共享信息

3. 下标处理

• 玩偶从 0 开始编号
• f_pre[i] 包含前 $i$ 个玩偶（编号 0 到 $i-1$）
• f_suf[i] 包含后 $n-i+1$ 个玩偶（编号 $i-1$ 到 $n-1$）

总结

这道题通过 前后缀预处理 + 单调队列优化，将原本 $O(q \cdot n \cdot m)$ 的暴力算法优化到 $O((n + q) \cdot m)$，是处理"带删除的背包问题"的经典方法。核心在于利用预处理避免重复计算，以及使用单调队列高效处理多重背包。