CF1481E

Zpair · 2023-11-15 16:46:29 · 题解

首先有一个简单的性质，就是一本书只会被放在最后一次。

所以我们考虑把所有被放在后面的书单独拿出来，然后按颜色排完序再放回去。

然后发现所有被拿出来的书中，最多有一种颜色的书没有全部被拿出来。且如果存在一种颜色的书没有被全部拿出来，则剩下的这种颜色的书应该被全部排在最后。

我们称完全留下的颜色为 A 类颜色，完全被拿出的颜色为 B 类颜色，排在最后未被完全拿出来的颜色为 C 类颜色。

然后考虑每一种颜色的性质。

显然 A 类颜色对应的一定是一段区间，然后这段区间包含所有这种颜色的书，区间中所有其他颜色的书都需要被拿出来。

然后就相当于把整个序列划分为若干段 A 类颜色对应区间，然后中间可以有空隙，但是 A 类颜色区间不能有交。然后 A 类颜色区间中的其他颜色都必须被选为 B 类颜色，除了最后的颜色可以不拿出来，因为它可以作为 C 类颜色。

可以结合下面的图理解一下。

图中 A 类颜色为红色，B 类颜色为蓝色，C 类颜色为绿色。

按上面的划分方式下标为 2,3,4,6,7,9,10 的数需要被拿出。

设：f_i 表示 [i,n] 的区间合法的最大未被拿出个数，S(l,r,x)=\sum_{i=l}^r [a_i=x].

然后若 i 作为一个颜色的最左端点，则可以将其作为一个 A 类颜色段。所以有 f_i \leftarrow f_{r_{a_i}+1}+S(i,r_{a_i},a_i).

否则可以将 i 作为一个 C 类颜色段，此时需要将 i 以后所有除了 a_i 以外的颜色全部拿出，所以有：f_i \leftarrow S(i,n,a_i).

然后可以将 a_i 作为一个 B 类颜色，所以有 f_i \leftarrow f_{i+1}.

考虑这些转移的合法性。C 类颜色段一定只有一个，A 类颜色段一定不交，然后所有 A 类颜色段中间的点一定不会作为 A 类颜色，容易发现从这几个条件就可以完全限制序列的合法性。

转移的实现是平凡的，时间复杂度为 O(n)。