题目理解

我们有一个长度为 $N-1$ 的序列 $B$，要求统计长度为 $N$ 的序列 $A$ 的数量，满足：

1. 子序列条件：$A$ 删掉一个元素后等于 $B$
2. LIS 条件：存在一个排列 $H$，使得 $A_i$ 是以 $H_i$ 结尾的最长递增子序列的长度

关键观察

1. LIS 条件的转化

对于排列 $H$，设 $f(i)$ 是以 $H_i$ 结尾的 LIS 长度，那么 $f$ 序列必须满足：

• $f(i) \ge 1$
• 如果 $f(i) = k$，那么存在某个 $j < i$ 使得 $H_j < H_i$ 且 $f(j) = k-1$
• 对于每个 $k$，第一次出现 $f(i) = k$ 的位置 $i$ 对应的 $H_i$ 必须小于所有后面 $f(j) = k$ 的 $H_j$

实际上，$f$ 序列对应着一个LIS 构造过程：当我们按顺序处理排列时，维护每个 LIS 长度的最小末尾元素。

2. 已知结论

对于一个序列 $A$，存在排列 $H$ 使得 $A_i$ 是以 $H_i$ 结尾的 LIS 长度，当且仅当：

• $A_1 = 1$
• $A_i \le A_{i-1} + 1$ 对所有 $i \ge 2$
• 对于每个 $k \ge 1$，第一次出现 $A_i = k$ 的位置 $i$ 必须小于所有后面 $A_j = k$ 的位置 $j$ 对应的 $H_j$（这实际上意味着序列必须满足某种单调性）

更简洁地说：$A$ 必须满足 $A_1 = 1$ 且 $A_i \le \max\{A_1, \dots, A_{i-1}\} + 1$。

3. 问题重述

现在问题变成：统计序列 $A$ 的数量，使得：

1. $A$ 的长度为 $N$，$B$ 的长度为 $N-1$，且 $A$ 删掉一个元素等于 $B$
2. $A_1 = 1$
3. $A_i \le \max\{A_1, \dots, A_{i-1}\} + 1$ 对所有 $i \ge 2$

算法设计

1. 分析删除位置

设 $A$ 删除了位置 $p$ 后得到 $B$，那么：

• 对于 $i < p$：$B_i = A_i$
• 对于 $i \ge p$：$B_i = A_{i+1}$

2. 必要条件

由于 $A$ 必须满足 $A_1 = 1$ 且 $A_i \le \max_{j<i} A_j + 1$，我们可以推导出：

• 设 $M_i = \max\{A_1, \dots, A_i\}$
• 那么 $A_{i+1} \le M_i + 1$

3. 动态规划思路

我们可以枚举删除的位置 $p$，然后检查 $B$ 序列是否能够插入一个合适的值 $x$ 在位置 $p$ 使得整个序列满足条件。

但是直接枚举 $N \le 10^6$ 个位置，每个位置检查 $O(N)$ 会超时。

4. 关键观察

实际上，满足 LIS 条件的序列 $A$ 必须满足：每当 $A_i = k$ 是第一次出现时，所有后面的 $A_j = k$ 必须对应着递增的 $H_j$。

这意味着：如果我们在位置 $p$ 插入值 $x$，那么：

• $x$ 不能破坏已有的"第一次出现"结构
• $x$ 必须满足 $x \le M_{p-1} + 1$ 且 $x \ge 1$

5. 高效算法

我们可以预处理：

• 前缀最大值 $preMax[i] = \max\{B_1, \dots, B_i\}$
• 后缀最大值 $sufMax[i] = \max\{B_i, \dots, B_{N-1}\}$

对于每个删除位置 $p$，可插入的值 $x$ 必须满足：

1. $x \le preMax[p-1] + 1$（基于前缀条件）
2. 如果 $x > preMax[p-1]$，那么 $x = preMax[p-1] + 1$（因为不能跳过数字）
3. 插入后不能破坏后缀的 LIS 结构

实际上，经过分析可以发现：对于大多数位置 $p$，可插入的值 $x$ 是唯一确定的，或者只有很少的选择。

高效解法（基于官方思路）

实际上，经过深入分析，这个问题有 $O(N)$ 的解法：

1. 序列 $A$ 必须满足 $A_1 = 1$ 且 $A_i \le \max_{j<i} A_j + 1$
2. 当我们在位置 $p$ 插入值 $x$ 时：
   • 如果 $p = 0$：$x$ 必须是 1
   • 如果 $p > 0$：$x \le \max\{B_1, \dots, B_{p-1}\} + 1$
3. 此外，插入不能破坏 LIS 的结构，这意味着对于每个值 $k$，所有 $A_i = k$ 必须对应着递增的 $H_i$

最终的高效解法需要维护每个值最后一次出现的位置等信息，在 $O(N)$ 时间内统计答案。

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

总结

这道题的关键在于：

1. 理解 LIS 序列的性质：$A_1 = 1$ 且 $A_i \le \max_{j<i} A_j + 1$
2. 分析删除操作的影响：枚举删除位置，检查可插入的值
3. 维护 LIS 结构：确保插入的值不破坏"第一次出现"的单调性

通过深入分析 LIS 序列的组合结构，我们可以得到高效的计数算法。