单调

超级神仙题。

题意

给你一个序列 \(a_1\dots a_n\)，值域为 \([1,3]\) 最大化选择的不交的合法子序列数，一个合法的子序列是 \(1,2,3\) 或 \(3,2,1\)， \(n\leq 10^5\)，输出方案。

这个题乍一看建不出网络流模型，也没有什么像样的 dp 做法，所以考虑一些神奇的贪心或者结论。

\(\texttt{1\反悔贪心}\)

考虑从左到右处理出每个前缀的答案，加入一个新的数字最多使答案增加 1。

考虑贪心：

直接记录目前 \(1\) 的集合 \(3\) 的集合，\(12\) 的集合 \(32\) 的集合，然后贪心地匹配，来了个 \(2\) 就随便给 \(1\) 或者 \(3\) 凑。

这个也很显然是错的，有两个错点：

第一个是 \(2\) 的问题：\(\texttt{3123}\) 如果把这个 \(2\) 给了 \(3\)，后面出现 \(3\) 了本身可以形成 \(\texttt{123}\) 的，对于这个错点我们可以发现目前所有 \(1,3\) 后面的 \(2\) 来说，\(1,3\) 的集合一定都可以公用这些 \(2\)，或者都不能接上这些 \(2\)，否则一定会形成 \(1,2,3\) 或 \(3,2,1\)，于是我只需要记录所有后方的 \(2\) 和前方的 \(2\) 的位置集合。

第二个问题是贪心的形成不一定对：

一个例子是 \(\texttt{123231}\) 。 贪心的匹配出了 \(\texttt{123}\)，后面剩下的部分就不合法了，而选择 \(\texttt{12__3_,__32_1}\) 这两个串是更优的。 这启示我们在这个 \(2\) 出现时反悔之前的操作：

若之前有 \(\texttt{123}\) 或 \(\texttt{321}\) 且有单独的未匹配的 \(2\)，这一位是 \(1\) 或者 \(3\)，则我们可以改变匹配的方式将类似 \(\texttt{123 + 23}\) 变成 \(\texttt{123 + 32}\)。

例：

\(\texttt{123+23}\to\texttt{12__3 + __23_ }\) ，这样是不劣的，因为开始那样 出现在 \(1,3\) 前面的 \(2\) 必定不可能对答案贡献，形成了 \(\texttt{12,32}\) 后可能产生贡献。

于是思路就出来了：

若该数为 \(2\) ：

若目前 \(1,3\) 都有对应的 \(2\) 了，就将 \(2\) 放入“单独 \(2\)”集合，可能在后方被已经形成的串用作反悔，否则放入“已用 \(2\)”集合，可以被目前所有 \(1,3\) 共用。

若该数为 \(1\) ：

（优先级最高）若能形成一个 \(1,2,3\) 一定不劣。

（优先级次高）若在“单独 \(2\)”集合非空，从其中前面拿出一个 \(2\)，找到其对应的合法串做反悔形成 \(12\)，这样一定不必放单独的 \(1\) 劣。

（优先级最低）放入单独的 \(1\) 中为后面做匹配。

该数为 \(3\) 的情况与 \(1\) 中心对称。

实现较为复杂，适当使用队列可以做到 \(O(n)\) ，一个很大的优点是它可以处理出每个前缀的答案且是复杂度线性。

\(\texttt{2\神奇结论}\)

一个好像很显然又无法想到的结论是：

对于每一对 \(\texttt{121},\texttt{323}\) 无论位置关系总存在一种方案调整配对关系形成两个合法串，具体讨论可以在纸上模拟一下。

也就是说我们先把 $\texttt{121,123,321,323} $ 全部拿出来，然后将 \(\texttt{323,121}\) 交换至合法，然后对于剩余的 \(\texttt{121 或 323}\) 和剩余的 \(3\) 和 \(1\) 匹配在一起，可以证明这样是正确的，因为 \(\texttt{123}\) 的个数在这种情况下总被 \(1,3\) 及 有意义的 \(2\) 中的至少一者限制。

现在转化后的问题 \(1\) 和 \(3\) 等价了我们把他们都当作 \(1\)，然后就是要选择一些以 \(1\) 为端点的线段并匹配中间的一个 \(2\) 。

这个问题可以而二分答案解决：二分答案 \(k\)，则一定是将前缀中 \(i\) 个 \(1\) ，后缀中的第 \(i\) 个 \(1\) ，以及能供匹配的最靠前的 \(2\) 匹配，证明可以由两个数的情况归纳推广而来。

好像还可以做到线性，但我不太会。

复杂度 \(O(n\log n)\)，实现那个调整 \(\texttt{121,323}\) 可以通过循环顺序较为简单地实现。

\(\text{More:}\)

收录于 超级无敌神仙炫酷无敌原神大王好题 。

有一说一这种题虽然很好，但是像喵了个喵这种这种难想还难写的题还是少点吧。