CF1768C 题解

\(\mathcal Solution\)

【题意】

题目要你构造两个序列 \(p, q\)，满足 \(\max\{p_i, q_i\}=a_i\)。

【分析】

如果满足 \(\max\{p_i, q_i\}=a_i\)，则满足 \(p_i=a_i, q_i\le a_i\) 或者 \(q_i=a_i, p_i\le q_i\)。

引理 \(1\)：如果有解，那么 \(p_i = a_i\) 还是 \(q_i = a_i\) 都是有解的。

证明：

因为有解，所以对于 \(\forall i(1\le i\le n)\) 都满足 \(p_i=a_i\) 或者 \(q_i=a_i\)。

如果 \(p_i = a_i\) 有解，则我们对于 \(\forall i (1\le i\le n)\) 进行 \(\operatorname{swap}(p_i, q_i)\)，也一定有解，这种情况就是 \(q_i=a_i\)，\(\operatorname{swap}(p_i, q_i)\) 就是交换两个数。

然后我们根据性质 \(1\)，枚举每个数 \(a_i\)，然后判断 \(p_i\) 序列中是否存在 \(a_i\)，不存在，则把 \(a_i\) 加入序列 \(p\) 中，否则，如果 \(q\) 序列中出现了 \(a_i\)，则无解，否则将 \(a_i\) 加入序列 \(q\) 中。

接着我们看如何填入其他数。

我们贪心的考虑，一定是选能选的数最大的那个。

然而直接暴力枚举是 \(\mathcal O(n^2)\)，会 TLE，我们考虑优化。

我们是否能枚举小于一次就找到没有用过的最大值。

这个可以用并查集来维护，即一个数变成用过，判断其左边和右边是否为用过，如果用过，则合并成一个集合，然后维护每一个集合中的左端点。

那么找最大值就等价于找 \(a_i\) 所在的集合的左端点减 \(1\)，还要特判 \(a_i\) 没用过的情况。

具体实现见代码。