题解

思路

扫描序列时，记录当前只出现过一次的颜色集合。两处前缀的集合相同，当且仅当它们之间的子段包含若干种颜色的完整两次出现，称为平衡子段。

当前集合第一次回到空集时得到一个最外层块。每个最外层块至少要初始打开一盏灯，不同块互不影响，因此最小集合大小等于块数。

在块 $[l,r)$ 内，从左向右计数。若从当前位置开始存在严格短于整个块的平衡子段，就跳过该子段；否则当前位置可作为单独点亮整个块的起点，计数并右移一位。所得计数就是该块可选的起始灯数量，各块计数相乘即为方案数。

做法

子任务 1

枚举所有初始集合，反复执行两类开灯规则直至不再变化，统计能打开全部灯泡的最小集合。复杂度为 $O(2^{2n}n^2)$。

子任务 2

用长度为 $n$ 的位向量精确表示当前颜色集合，以有序映射记录每种前缀状态的最近位置。每次状态重复就得到可跳过的平衡子段。复杂度为 $O(n^2\log n/64)$。

子任务 3

用持久化二叉树表示颜色集合。每次只翻转一个叶子；把相同的左右儿子对规范化为同一个节点编号，因此根编号完全相同当且仅当两个集合相同。一次翻转只修改 $O(\log n)$ 个节点，再按根编号记录最近前缀即可。

正确性证明

一个最外层块不会通过别的块中的同色灯被打开，所以每块至少选择一盏灯。若某位置不被任何从该位置开始的真平衡子段包住，则打开其同色灯后，已打开区间会依次吸收块中的所有非封闭部分，最终覆盖整块；反之，真平衡子段与外部没有跨界颜色，不能由该位置单独跨越，故应整体跳过。扫描恰好计数所有能单独点亮该块的位置。各块独立选择，最小值为块数，方案数为各块计数之积。

复杂度

满分算法每组时间复杂度为 $O(n\log n)$（哈希表操作为均摊常数），空间复杂度为 $O(n\log n)$。