CF EDU 139 略解

E

观察到 \(0\&(1,2,3)=0\)，除此之外只剩下 \((1\&2=0)\)

然后我也不知道有什么用了。

这个暴力应该是非常好写的，直接统计 \(0/1/2/3\) 的个数即可。

不对啊，感觉这个暴力怎么写出来还需要链表呢。。。

不重要，但是我总感觉这个拆分之后的序列个数应该不会很大(?

草了，\(n\) 个 \(0\) 就破产了。

emmm，\(1\) 只有在末尾没有 \(1,3\) 的时候才能新建一个序列，\(2\) 同理，3只有在全是0的时候才会新建一个序列。

所以作为末尾，显然有了 \(0\) 那么这个序列便不会产生更多的贡献了，也就是说0只会单独成为一个长度为 \(1\) 的序列。

故我们只需要考虑 \(1，2，3\) 之间的关系。

显然 \(3\) 在有一个末尾 \(\in[1,2,3]\) 的情况之后，便不可能去新开序列。

观察到一旦出现了一个3的末尾，那么他在之后一定会变成离他最近的 \([1,2]\)，后面和他相同的，再之后再变成3，再变成离他最近的 \([1,2].....\)

也就是说，\(3\) 一定都会出现在第一个序列里面。

并且每个\(3\) 一定会伴随着他之后第一个 \(i,a[i]\in{1,2}\) 出现在这个序列里面。

哦，也就是说在排除 \(0\) 的情况下，最多只有3个序列，一个是 \(3\) 和它后面的第一个 \([1,2]\) 和后面和这个 \([1,2]\) 相同的，剩下两个一个全是 \(1\) 一个全是 \(2\)

所以我刚刚那个拆分之后序列个数不会很大的猜想只要排除 \(0\) 就是对的。

那就简单了啊，我先把 \(0\) 删完，然后写三个双指针，分别代表有 \(1，2，3\) 个序列的最近的r在什么位置。

其实也不能直接删，太麻烦了，没必要，可以直接忽略掉他。

额，貌似第一个双指针没什么毛用，其实只需要后两个。

稍微注意一下第二个最近的 \(r=i+1\) 的时候，需要全部重新更新。

比如 \([1，2，3]\) 这种情况，\(i=1\) 时，第二个 \(r=2\) ，而 \(i++\) 之后 \(1\) 没了，可能你就不能直接用你的双指针动态维护的那些东西了。

CTM这样写第三个双指针他不是单调不减的我破防了。

我不管了，我要乱搞，我随便写些特判就行了。

倒着写双指针貌似是对的，但是我一点也不想改了。

好吧，在发现只会有最多三个序列之后其实可以DP，但是我不想改了。

大功告成。

\(\text{My Submisson}\)