[ROI 2023] 峰值 (Day 1)

(mathbf{Part. -1})

翻译自 ROI 2023 D1T3。

如果对于所有 (1 le j < i)，都有 (a_j < a_i)，则称 (a_i) 为峰值。

如果对于所有 (1 le j < i)，都有 (a_j > a_i)，则称 (a_i) 为反峰值。

给定大小为 (n) 的排列 (p_1,p_2,dots,p_n)。需要将其分为两个非空子序列 (q) 和 (r)。每个元素 (p) 必须恰好被分到一个子序列中。你需要最大化 (q) 中的峰值数量和 (r) 中的反峰值数量之和。

(1 leq n leq 2 times 10^5)。

(mathbf{Part. 1})

我们按顺序考虑每一个 (a_i)。由于我们要把序列划分成两个子序列，分别是递增和递减，所以我们定义 (mx) 表示当前考虑到第 (i) 个数的递增序列中最后一个值，(mn) 表示当前考虑到第 (i) 个数的递减序列中最后一个值。显然，我们可以通过储存这两个值来进行 DP。设 (f_{i, mx, mn}) 表示当前考虑到第 (i) 个数的 (mx) 和 (mn) 值，则转移是朴素的。

我们想要更快的算法，于是我们考虑研究 DP 转移的过程（也是按顺序对 (a_i) 分配的过程）。对于每一个数 (a_i)，当前的 (mx,mn) 我们已经知道了：

• 对于 (mx < mn) 来说：
  • 如果 (mx < mn < a_i)，则我们将 (a_i) 加到 (mx) 数列里会更新，加到 (mn) 数列里没影响。
  • 如果 (a_i < mx < mn)，则我们将 (a_i) 加到 (mx) 数列里没影响，加到 (mn) 数列里会更新。
  • 如果 (mx < a_i < mn)，则加到任何一个数列都会更新。(^{{color{red}(1)}})
• 对于 (mn < mx) 来说：
  • 如果 (mn < mx < a_i)，则我们将 (a_i) 加到 (mx) 数列里会更新，加到 (mn) 数列里没影响。
  • 如果 (a_i < mn < mx)，则我们将 (a_i) 加到 (mx) 数列里没影响，加到 (mn) 数列里会更新。
  • 如果 (mn < a_i < mx)，则加到任何一个数列都没有影响。

对于两种情况，显然只有 (a_i) 在中间的时候情况不同。似乎如果更新少一点更简单，所以我们考虑 (mn < mx)。

(mathbf{Part. 2})

我们考虑 (mn < mx)。对于这种情况，我们发现，对于每个数，如果它可以但是不用在 (mx) 或者 (mn) 数列中的话，它可以选择不影响答案。因此，对于所有后面 (> mx) 的数，我可以选择一些来构成最长上升子序列，其他的划分到 (mn) 去，不对答案造成影响。(< mn) 的数同理(^{color{red}(2)})。容易发现，这其实是 (mathbf{LIS}) 和 (mathbf{LCS}) 问题，而这个问题我们可以用 (mathbf{BIT}) 轻松计算出每个 (a_i) 开头的 (mathbf{LIS,LCS}) 值。

但是对于 (mx < mn)，由于 (color{red}(1)) 的存在，并不是每个数都能选择不影响序列。如果我们直接考虑研究 (mx < mn) 的转移过程，那是没有任何性质的(^{color{red}(3)})。但是，如果我们观察答案整体的结构，我们发现 (mx > mn) 和 (mn > mx) 分别是这个序列中的前缀和后缀部分，所以不难想到枚举分界点。

（为了方便区分，我们后文将 (mx < mn) 的部分称为前面的部分，(mx < mx) 的部分称为后面的部分）

我们考虑枚举分界点 (x)。如果我们要求后面的部分，它的答案，那么由 (color{red}(2))，我们需要知道 (mn) 和 (mx) 的值来划分后面的数分别可以分到哪一个数列。因此，我们考虑枚举在分界点 (x) 选择完之后，(mn,mx) 的值的。（此时，(mn < mx)）

接着，我们考虑前面的部分怎么求。首先，由 (color{red}(3))，前面的操作过程没什么救，但是我们知道前面 (mx < mn) 啊！由于所有 (mx) 序列的所有数都 (leq mx)，(mn) 序列的所有数都 (geq mn)，而 (mx <mn)，所以 (mx) 序列的所有值都小于 (mn) 序列的所有值！因此，我们再考虑枚举分界点 (x) 还没选择前，(mn,mx) 的值。这样，我们可以预处理出前面所有 (leq mx) 的数的前缀最大值个数，和所有 (geq mn) 的前缀最小值的个数。

当然，实际上你在枚举 (mn,mx) 的时候，有可能存在 (a_i)，使得 (mx < a_i < mn)。这种情况显然不合法！因此，我们枚举的 (mx) 和 (mn) 需要保证不存在 (a_i) 使得 (mx < a_i < mn)(^{color{red}{(4)}})。

但这样复杂度直接起飞，非常不好。考虑我们都枚举了什么东西。

• 分界点 (x)
• 分界点选择之前 (mx,mn) 值
• 分界点选择之后 (mx,mn) 值

我们发现，分界点选择之前的 (mx,mn) 和之后的 (mx,mn) 肯定有很多重复啊！假设 (x) 选择之前是 (mx,mn)，那 (x) 选择，肯定要么更新 (mx)，要么更新 (mn)，然后都是变成 (a_x)，所以实际上我们只需要枚举 (mx,mn)，然后分类讨论一下即可。

我们明明已经找到了这么多性质，时间复杂度还是 (mathcal{O}(n^3))。怎么回事呢？但其实不然。由 (color{red}(4))，我们知道 (mx,mn) 肯定是前面的 (a_i) 的值，而我们不能存在 (a_i) 在 (mx,mn) 之间，所以实际上 (mx) 是 (mn) 的后继。因此，你只需要枚举 (mx,x) 两个值即可，复杂度为 (mathcal{O}(n^2))。

我们考虑这个算法的细节。首先，枚举 (x,mx)，则 (mn) 是很容易通过维护 (mathbf{set}) 算出来的。然后，我们发现对于一个 (mx)，肯定在前面出现过，而且这个 (mx) 后面的数是没用的，所以我们可以对于每个 (a_i leq mx)，预处理出所有 (leq mx) 的数的前缀最大值个数，(mn) 同理。对于后面的部分，我们可以通过 (mathbf{BIT})，求出以每个 (a_i) 为开头的 (mathbf{LIS,LCS})。然后，由于我们要求以 (x) 为开头的最长子序列，和以 (i > x,a_i < mn) 或者 (i > x, a_i > mx) 开头的最长子序列，因此我们按顺序扫一下 (mx) 就可以快速求出。

(mathbf{Part. 3})

我们考虑优化这个算法。

我们大概的思路是：枚举一个值，另一个值数据结构维护，所以我们可以枚举 (x)。结果我们发现，枚举 (x) 完全不可做！！！？？？这怎么办？

这时候最重要的一点：抛弃前面的所有思想，我们考虑枚举什么更优秀！但此处的抛弃并不是真正的抛弃，因为你已经发现了很多性质，赛场上你是不会忘掉的。

我们考虑枚举 (x) 为什么不优秀。枚举 (x)，给我们提供了 (mx < mn < a_x) 或 (a_x < mx < mn) 的信息，让我们知道从 (i) 开始进入后面的部分，但是我们不知道 (mx,mn)；不知道 (mn) 后面应该找什么数（这里就很离谱了：我们不知道 (mn)，还要对于 (x > i,a_x < mn) 来二位数点！），但是知道 (mx) 后面一定是 (i)。如果枚举 (mx) 的话，如果 (mn) 在 (mx) 的右边，那我们不能知道 (mn) 是什么。

我们对于 (mx,mn) 维护的信息是不平衡的，但是我们又要通过 (mx) 求出来 (mn)。于是，我们应该要枚举一个点，这个点左边涵盖了 (mn,mx)，右边是我们要找的转折点 (x)。如果 (mx) 在 (mn) 左边，这个 (x) 可以是 (mx)，否则可以是 (mn)……对！我们可以枚举 (mn) 和 (mx) 最靠右的那个点！

假设我们枚举了 (x)，其中 (mn,mx) 都在 (x) 左边，且其中有一个是 (a_x)。由 (color{red}(4))，这两个值在 (x) 左边的值域上肯定是相邻的，所以我们可以通过 (mx) 求出来另一个 (mn)。那么，我们分类讨论 (x) 是 (mx) 还是 (mn)，对于每种情况，我们还要考虑是 (mn) 还是 (mx) 的更新造成了 (mn,mx) 的大小关系变化。因此，我们枚举 (x)，然后分类讨论四种情况。不妨设 (a_x) 是 (mx)，我们算出来了 (mn)，(mx) 跳完后超过了 (mn)，则跳的下标 (p) 要满足 (p > x, a_p > mn)，然后求 (mathbf{LIS}(p)) 的最大值，这是经典的二位数点。

(mathbf{Part. +infin})

这份代码是 @Albert_Wei 写的，本人还没写，写了 update。

int n, p[N], res[N][2], l[N], r[N];  struct BIT {     int tr[N];     void init() { F(i, 1, n + 1) tr[i] = 0; }     void modify(int x, int y) { for (; x <= n + 1; x += (x & -x)) tr[x] += y; }     int query(int x) { int ans = 0; for (; x; x -= (x & -x)) ans += tr[x]; return ans; } } S; struct BIT2 {     int tr[N];     void init() { F(i, 1, n) tr[i] = 0; }     void modify(int x, int y) { for (; x <= n; x += (x & -x)) Fmax(tr[x], y); }     int query(int x) { int ans = 0; for (; x; x -= (x & -x)) Fmax(ans, tr[x]); return ans; } } U, V;  void solve() {     n = read();     F(i, 1, n) p[i] = read();     S.init();     set<int> st;     st.insert(0), st.insert(n + 1);     F(i, 1, n) {         l[i] = *(-- st.lower_bound(p[i])), r[i] = *st.upper_bound(p[i]);         S.modify(l[i] + 1, 1), S.modify(r[i] + 1, -1);         res[i][0] = S.query(p[i] + 1), res[i][1] = S.query(p[i]), st.insert(p[i]);     }     int ans = 0;     U.init(), V.init();     G(i, n, 1) {         if (r[i] != n + 1) Fmax(ans, res[i][0] + U.query(n - r[i]) + V.query(r[i]));         Fmax(ans, res[i][0] + U.query(n - p[i]) + V.query(p[i]));         Fmax(ans, res[i][1] + U.query(n - p[i]) + V.query(p[i]));         if (l[i]) Fmax(ans, res[i][1] + U.query(n - l[i]) + V.query(l[i]));         U.modify(n - p[i] + 1, U.query(n - p[i]) + 1);         V.modify(p[i], V.query(p[i]) + 1);     }     F(i, 0, n) Fmax(ans, U.query(n - i) + V.query(i));     cout << ans << 'n'; }