题解

思路推导

若最后一次清空发生在前缀 $[1,i]$，那么最终答案只由后缀 $[i+1,n]$ 决定。于是问题分成两部分：哪些前缀能够被安排成恰好清空，以及从每个位置开始、在不再清空的条件下最多能留下多少苹果。

从右向左扫描后缀。在遇到两个已知集合包含同一种类时，更长后缀必然发生清空，扫描终止。若无冲突且后缀含有遗忘商店，可把某一家指定为所有尚缺种类、其余指定为空，从而留下 $m$ 个；否则留下已知集合并集大小。

前缀可清空性可以用最后出现位置递推。维护每个苹果种类最后出现的商店、最后一家遗忘商店、此前已经无法跨越的重复位置，以及每个前缀之前最近的可清空前缀。扫描一个已知集合时，其元素或遗忘商店的最近出现位置给出本次可能触发清空的位置；只有这个位置之后存在尚未被旧重复阻断的可清空前缀，当前前缀才可清空。遗忘商店本身总能选择集合使当前前缀清空。

做法

子任务 1 枚举每家遗忘商店的全部 $2^m$ 个子集，直接模拟购物过程。

子任务 2 按上述递推做两次线性扫描，并为 $1\ldots m$ 的每个种类开最后位置和出现标记数组。其复杂度含 $O(\sum m)$ 初始化。

满分做法只为实际出现过的苹果种类保存最后位置与后缀标记，使用哈希表或平衡树消除 $O(\sum m)$ 初始化；这正是原约束不保证 $\sum m$ 时的关键。

正确性证明

右向左扫描时，在首次发现两个已知集合含同一种类之前，所有已知苹果两两不同。若这段后缀没有遗忘商店，最终数量就是其并集大小；若含遗忘商店，可让最后一个合适的遗忘商店补齐所有缺少种类而不产生重复，故最大值为 $m$。一旦已知种类重复，任何更长后缀都必然在其中发生清空，因此不能作为“最后一次清空之后”的后缀。

对前缀归纳。遗忘商店可根据进入时的背包选择集合制造重复，所以其结尾前缀可清空。已知商店只有在当前集合中的某种类曾在仍可能保留的区间出现，或此前存在遗忘商店时才可能触发清空；最近出现位置刻画所有这些候选。旧重复位置之后若没有可清空前缀，则无论怎样指定遗忘集合都会提前破坏所需状态；反之，取最近可清空前缀即可构造出本次清空。递推条件因此充要。

枚举所有可清空前缀 $i$ 并取对应合法后缀最大值，覆盖且仅覆盖所有可能的最后一次清空位置，所以所得最大值即答案。

复杂度分析

设所有已知集合大小之和为 $K$。满分算法期望时间复杂度为 $O(n+K)$，空间复杂度为 $O(n+K)$；使用平衡树的独立实现为 $O((n+K)\log(n+K))$。