菜王的 blog

下文中令 $a$ 为题目中的 $c$ 序列。

考虑一对限制 $(x, y)$ 的本质是什么。根据题意得知，$\max_{i = 1}^x a_i < a_y$，且 $a_k \le \max_{i = 1}^x a_i(x < k < y)$，于是可以推出 $\max_{i = 1}^{y - 1} a_i < a_y$，也就是说。$a_k(x < k < y)$ 一定不是严格前缀最大值，而 $a_y$ 一定是严格前缀最大值。

于是我们可以 $O(n)$ 求出数组 $b$，$b_i = -1/0/1$，表示 $a_i$ 一定不是 / 不一定是 / 一定是 前缀最大值，或者推出矛盾（即一个位置同时应该是 $-1, 1$ 的情况），判无解即可。

考虑构造。首先我们考虑 $a$ 全都不确定的情况，此时是简单的，$b_i = 1$ 时令 $a_i = \max_{j = 1}^{i - 1} a_j + 1$，否则令 $a_i = 1$ 即可。

如果当前的 $a_i$ 确定了，那我们考虑判断合不合法。

1. 如果 $b_i = 1$ 且 $a_i \le \max_{j = 1}^{i - 1} a_j$ 则一定无解，因为我们在最小化字典序的同时最小化了前缀 $\max$。
2. 如果 $b_i = -1$ 且 $a_i > \max_{j = 1}^{i - 1}$，则我们考虑往前找到一个最大的 $p$ 使得 $a_p$ 未确定且 $b_i \ne -1$，令 $a_p = a_i$ 来满足 $a_i$ 的限制。如果找不到这样的 $p$ 那么显然无解；调整后 $a_p$ 可能会与 $[p + 1, i - 1]$ 中的一些位置的限制冲突，此时也一定无解。因为冲突的位置 $o$ 一定满足 $a_o$ 确定了，且 $b_o = 1$，而这样的位置相当于给前缀 $\max$ 设置了上界。

于是我们可以做到 $O(n)$ 构造并且判定是否有解。代码在这里。