P9139 题解

loverintime · 2023-03-07 20:00:40 · 题解

场切了， 并且是正解， 很高兴， 来写一篇题解。

但是爆搜过了

题意

给定一个长度为 4n 的序列 a_{1\sim 4n}， 其中 1\sim n 各出现 4 次， 问能否将其划分为两个完全相同的子序列。

题解

首先考虑一个弱化版： 如果每个数只出现两次。 考虑这个问题有没有什么简洁的方法。

令一个数 i 第一次出现的位置为 l_i, 第二次为 r_i， 那么有解的充要条件为任意两个 [l_i,r_i] 没有包含关系。

首先如果存在包含关系就一定无解（这两个数在两个序列中的出现顺序不同）。 否则可以将所有 l_i 划分到第一个序列中， r_i 划分到第二个序列中， 这样一定是正确的。 可以感性理解为任意两个数的出现顺序在两个序列中是相同的。

回到本题。 由于有 4 个数， 我们可以考虑将它们划分为两对然后做上面的构造。 可以发现无论这 4 个数如何划分， 都可以规约成两对不同颜色的情况。 并且可以显然地发现只有 (1,2)\&(3,4),(1,3)\&(2,4) 这两种划分方法， 因为 (1,4)\&(2,3) 已经无解了。

分析到这儿， 就可以想到 \operatorname{2-sat} 了。其中限制是区间不能包含。 将区间看成平面上的点， 和某一个区间之间有限制的区间就在一个矩形内部了，可以使用主席树来优化建图， 然后直接跑 \operatorname{2-sat} 就行了。 线段树建图优化 \operatorname{2-sat} 可以看 ARC069F。

时间复杂度 O(n\log n)。 常数可想而知。

但是爆搜过了。

也可以使用 cdq 分治来优化建图， 本质相同。 都比爆搜慢一万倍。

代码就不放了。 场上写的， 常数大还很丑。