F1

F2

• 我们先来考虑数列中全是 $p_i = i$ 的情况。（但凡有一个 $p_i \ne i$，则所有的 $p_i = i$ 也能够被确定在哪边，所以不用这样特别考虑。）
  对于分割点所在的前面一个 $p_i = i$，显然最后的集合会存在一段 $1, 2, \dots, p_i$ 的前缀，否则不合法；对于后面一个也是一样的，存在一段后缀。因此我们只需要考虑每个区间内的分割方案。
  更进一步地，我们能发现对于 $a_i = i, a_j = j (i < j)$，夹在它们中间的 $j - i - 1$ 个元素必然是 $i + 1, \dots, j - 1$ 。自证不难。那么我们考虑若我们在这两个元素之间断开，中间这些东西怎么分。显然就是选一些位置分给左边，选一些位置分给右边，然后按一定顺序填数。
  对于中间有 $m$ 个元素的 gap，方案数显然是 $2^m$ 。然后对于单调上升的序列我们要特判，所以减去单调划分的方案数 $m + 1$。
• 然后考虑存在 $p_i \ne i$ 的情况。
  如前文所述，只要存在一个 $p_i \ne i$ 就必然能够确定所有的 $p_i = i$ 的颜色。比较简单，不妨自己推理一下。
  我们考虑按所有确定的值将序列划分为若干段，对于每一段单独计算贡献。
  考虑 $O(n^2)$ (?) 的递推怎么做。可以设计状态 $f_{i, j}$ 表示红的现在放到了 $i$ ，蓝的现在放到了 $j$ 。每次转移相当于是下标偏移+权值乘上某个数。我们直接显式暴力维护初始的 $O(n)$ 个状态，然后对于每段考虑。
  • 对于这段两端颜色相同的：
    我们可以直接得到这段里面两个颜色中间各需要加的个数（下标的偏移量以及下标取 max），以及最后走到了哪里（乘数）。注意到对于任何状态这些东西是一样的，不妨直接打 tag。
  • 对于这段两端颜色不同的：
    我们可以得到右边的那个颜色走到了哪里，但是转移的系数现在和左边那个颜色的数量有关了，我们不能直接打 tag。所以其实可以直接对于目前我们存储的状态暴力转移。
    为什么这样做的复杂度是对的呢？很容易注意到对于长度（中间不确定的个数）为 $m$ 的区间，每次转移保留的有效状态只有 $O(m)$ 个，即下一次处理的复杂度与这个区间的长度线性相关。所以整个复杂度事实上是 $O(n + \sum m) = O(n)$ 的。
  最后枚举剩下来的每个状态即可。
  注意序列的两端需要额外添加两个哨兵节点，以处理最开始和最末尾一段未确定元素的贡献。