问题重述

给定一个 $1$ 到 $N$ 的排列 $p$，和一个长度为 $N-1$ 由 U 和 D 组成的字符串 $s$。

要求找到最长的子序列 $a_0, a_1, \dots, a_K$，使得对于每个 $j = 1, \dots, K$：

• 如果 $s_j = \text{'U'}$，则 $a_{j-1} < a_j$
• 如果 $s_j = \text{'D'}$，则 $a_{j-1} > a_j$

输出最大的 $K$。

---

关键观察

1. 问题本质

这是带模式的最长交替子序列问题。模式由字符串 $s$ 指定，决定了相邻元素之间必须是上升还是下降关系。

2. 暴力 DP

最直接的想法是定义： $dp[i][k]$ = 考虑前 $i$ 个元素，匹配了模式的前 $k$ 个字符，且以 $p_i$ 结尾时的最小/最大值（取决于当前模式）

但状态数 $O(N^2)$ 对于 $N \le 3\times 10^5$ 不可行。

---

核心解法

1. 状态重新设计

关键洞察：我们只关心对于每个模式位置 $k$，能够达到该位置的所有子序列的最后一个元素的值。

定义两个数组：

• $up[k]$ = 匹配了模式的前 $k$ 个字符，且最后一个字符满足当前模式要求（即如果 $s_k = \text{'U'}$ 则要求上升）时，最后一个元素的最小值
• $down[k]$ = 匹配了模式的前 $k$ 个字符，且最后一个字符满足当前模式要求（即如果 $s_k = \text{'D'}$ 则要求下降）时，最后一个元素的最大值

这样设计的目的是：

• 对于上升转移，我们希望最后一个元素尽可能小，为后续的上升留出空间
• 对于下降转移，我们希望最后一个元素尽可能大，为后续的下降留出空间

2. 转移过程

我们按顺序处理排列中的每个元素 $x = p_i$：

对于每个模式位置 $k$：

情况 1：如果 $s_{k+1} = \text{'U'}$（下一个需要上升）

• 可以从 $up[k]$ 转移：如果 $x > up[k]$，则 $up[k+1] = \min(up[k+1], x)$
• 可以从 $down[k]$ 转移：如果 $x > down[k]$，则 $up[k+1] = \min(up[k+1], x)$

情况 2：如果 $s_{k+1} = \text{'D'}$（下一个需要下降）

• 可以从 $up[k]$ 转移：如果 $x < up[k]$，则 $down[k+1] = \max(down[k+1], x)$
• 可以从 $down[k]$ 转移：如果 $x < down[k]$，则 $down[k+1] = \max(down[k+1], x)$

3. 初始化

• $up[0] = 0$（实际上用一个极小值，表示还没有任何元素）
• $down[0] = \infty$（用一个极大值）

当我们处理第一个元素 $x$ 时：

• 可以直接开始一个长度为 1 的子序列
• 根据 $s_1$ 是 U 还是 D 来初始化 $up[1]$ 或 $down[1]$

---

算法优化

1. 单调性观察

$up[k]$ 随着 $k$ 增加是非递减的（因为每次上升转移都会选择尽可能小的值） $down[k]$ 随着 $k$ 增加是非递增的（因为每次下降转移都会选择尽可能大的值）

2. 二分优化

利用单调性，我们可以用二分查找来快速找到能够进行转移的模式位置：

对于当前元素 $x$：

• 如果下一个模式字符是 U，找到最大的 $k$ 使得 $up[k] < x$ 或 $down[k] < x$
• 如果下一个模式字符是 D，找到最大的 $k$ 使得 $up[k] > x$ 或 $down[k] > x$

这样可以将复杂度从 $O(NK)$ 优化到 $O(N \log K)$，其中 $K$ 是最终答案。

3. 实际实现

维护两个数组 $up$ 和 $down$，初始时：

• $up[0] = 0$, $down[0] = \infty$
• 其他位置 $up[k] = \infty$, $down[k] = 0$

对于每个元素 $x$：

1. 在 $up$ 数组中二分找到最大的 $k_1$ 满足 $up[k_1] < x$
2. 在 $down$ 数组中二分找到最大的 $k_2$ 满足 $down[k_2] < x$
3. 设 $k = \max(k_1, k_2)$
4. 如果 $s_{k+1} = \text{'U'}$，则 $up[k+1] = \min(up[k+1], x)$
5. 如果 $s_{k+1} = \text{'D'}$，则 $down[k+1] = \min(down[k+1], x)$（这里需要对称处理下降情况）

---

复杂度分析

• 对于每个元素：两次二分查找 $O(\log K)$
• 总复杂度：$O(N \log K)$，其中 $K \le N$
• 由于 $N \le 3\times 10^5$，完全可行

---

总结

这道题的核心在于：

1. 状态设计：用 $up[k]$ 和 $down[k]$ 分别记录两种模式下的最优结尾值
2. 贪心思想：上升时选择尽可能小的结尾，下降时选择尽可能大的结尾
3. 单调性利用：$up$ 数组单调不减，$down$ 数组单调不增
4. 二分优化：利用单调性快速找到可转移的位置

通过将问题转化为维护两个具有单调性的数组，并利用二分查找进行高效转移，我们成功地将 $O(N^2)$ 的 DP 优化到了 $O(N \log N)$，解决了这个看似复杂的问题。