题解：P16354 「Diligent-OI R3 B」天际线

Deepsick · 2026-04-26 20:21:58 · 题解

Part 1

先考虑在 a 和 b 的限制下序列长什么样。

首先，找出第一个使 b_i=1 的 i，如果不存在这样的 i 则令 i=n+1。

如果某个 a=1 的点出现在了 i 的严格右侧，则无解，因为这要求两个数互相大于。

否则，从左到右考虑每个元素。如果当前点的 b 为 1，则只能选择未选的最大数；否则，为了使得字典序尽量小，需要选取未选的最小数。显然这个序列是符合条件的。

Part 2

再考虑 c 的影响。如果某个 c=1 的点同时也满足 a=1 或者 b=1，或者开头或结尾元素的 c 为 1，显然无解。否则，i 及其右边的元素本身就已经满足条件，只需要对前 i-1 个元素进行调整。

对于这些元素，由刚才的过程可以发现，初始时第 j 个数为 j。对于 c=1 的位置，我们需要让它左边的某个数比它大。于是可以从右到左扫描，遇到某个 c=1 的点就和它左边的元素交换。

容易发现这是字典序最小的排列，这可以通过考虑每个 c=0 的点及其后连续一串 c=1 的点组成的段来证明。

注意到我们确保了每段都占用了其左边的段未占用的最小若干个元素。显然不满足此条件的排列字典序只会更大；而在满足此条件的前提下，每段的第一个元素都必须是段中最大的，而在我们现在构造的序列中，段内其他元素单调递增，所以也不存在字典序更小的合法排列。