自动搬运

查看原文

来自洛谷，原作者为

	loverintime 你我只差半步成诗

搬运于2025-08-24 22:45:43，当前版本为作者最后更新于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 分治来优化建图， 本质相同。 都比爆搜慢一万倍。

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