P14459 [ICPC 2025 Xian R] Mystique as Iris 笔记

考虑满足什么条件的序列可以被删空。

一个数可以通过缩减左边或右边来减小自身，因此，任意一个 $\in (1,n)$ 的数都可以被缩到 $1$，任意一个不全为 $1$ 的连续段都可以被缩小到只剩一个数 $x$。

显然 $1$ $x$ 和 $x$ $1$ 两种都可以将序列删空，因此，不能被删空的序列同时满足以下两个条件：

• $a_1,a_n\ne 1$。
• $\mathrm{\forall }i\in (1,n),a_i=1\vee a_i\ge n$。

直接从前往后 DP 即可。

此外还有一种特殊情况：当序列全为 $1$ 且长度为奇数时，无法删空，判断一下是否存在这种特殊情况。

时空复杂度 $O(n)$。