题解：CF2205D

· · 题解

D - Simons and Beating Peaks

观点

题出的好！覆盖知识点广，题目有着切合实际的背景，解法比较自然。给出题人点赞！更重要的是数据基本正确，符合一道好题的基本标准！

题意

定义一个长 m 的数组 b 是 cool 的当且仅当在 b 数组不存在 b_{i}=\max(\{b_{i-1},b_{i},b_{i+1}\}) 的下标 i\in(1,m)。

给出一个长 n 的数组 a，求让 a 变为 cool 的数组的最少操作次数。

每次操作你可以令 a_{i}=\max(\{a_{i-1},a_{i},a_{i+1}\}) 并删除 a_{i-1} 或 a_{i+1}（空位自动按顺序补全），注意 i-1,i,i+1 都要在当前下标范围内。

Sol

首先，你可以敏锐地发现，如果我们以下标为 x 坐标，以值为 y 坐标，那么数组对应的这些点必须得满足“只有一个极低谷”或“沿 x 轴严格单调”的。

下标顺序 & 区间最大，很容易想到笛卡尔树啊。

对原排列建 \max 笛卡尔树：根是全局最大值；中序遍历顺序等于数组下标顺序；任一节点 u 的左子树元素都在 u 左侧、右子树元素都在 u 右侧，且 a_u 大于其子树中所有值。

把“当前还没被删掉”的元素看成原数组的一个子序列，保持相对顺序不变。

设最终留下的集合为 S，对应笛卡尔树的诱导子图。

主题：最终留下的点必须是一条根到叶路径。

断言 1： 若某个节点 u \in S 在 S 中同时保留了来自其左子树与右子树的元素，则最终数组不可能 cool。

证明： 因为中序顺序，S 中位于 u 左侧的最近邻一定来自左子树，右侧的最近邻一定来自右子树。又因 max-heap 性质，a_u 大于左右子树任意值，所以在最终数组里 u 必满足

\text{left}(u) < u > \text{right}(u),

即 u 是局部峰，违反 cool。证毕。

由断言 1 得：对任意 u \in S，在 S 里它的左右两侧最多只能保留一侧的后代。等价于：在树上每个点在 S 中度数（向下孩子数）最多 1，因此 S 必是若干条链的并。

因为全局最大值（根）永远不能被删除操作（即只能删峰的邻居，不删峰本身），且最终数组必须连通成一个序列，所以 S 只能是一条包含根的链；在有根树中这条链必为根到某个叶子的路径。主题证毕。

于是可行保留长度 \le 树的高度 h。

主题：任意根到叶路径都能通过合法操作留下。

取任意一条根到叶路径 P。我们说明能删到只剩 P。

从根开始沿 P 向下处理每个节点 u。设 v 是 u 在路径上的孩子（可能不存在）。我们要删掉 u 的“非路径侧子树”全部元素：

关键点：当非路径侧还存在元素、且路径侧也存在元素时，u 在当前数组中一定是局部峰：它左右最近邻分别来自左右两侧（由中序顺序），且这些邻居值都小于 a_u（\max 笛卡尔树的性质）。因此 u 满足三元组最大条件，可以执行操作并删除任意一侧的邻居，特别是删除非路径侧的邻居。

每次删除都会减少非路径侧剩余元素数，故该过程必在有限步内删空非路径侧。对路径上节点自顶向下重复，最终所有不在 P 上的点都被删光，剩下的恰为 P。主题证毕。

因此最长可保留长度 \ge h，结合必要性得到最长可保留长度 = h。

结合上面内容，我们便有了结论：

最少操作次数

= n - \max |S| = n - h,

其中 h 为原排列 \max 笛卡尔树的高度（根到叶最长路径长度）。

于是这题做完了。注意赛时可以去猜结论。

Code

代码非常短。

#include <bits/stdc++.h>
using namespace std;

auto main() -> signed {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n + 5);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        vector<int> l(n + 5), r(n + 5), p(n + 5);
        vector<int> st;
        for (int i = 1; i <= n; ++i) {
            int last = 0;
            while (!st.empty() && a[st.back()] < a[i]) {
                last = st.back();
                st.pop_back();
            }
            if (!st.empty()) {
                r[st.back()] = i;
                p[i] = st.back();
            }
            if (last) {
                l[i] = last;
                p[last] = i;
            }
            st.emplace_back(i);
        }
        int rt = st.front();
        while (p[rt]) rt = p[rt];
        vector<int> dep(n + 5);
        queue<int> q;
        dep[rt] = 1;
        q.emplace(rt);
        int h = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            h = max(h, dep[u]);
            if (l[u]) {
                dep[l[u]] = dep[u] + 1;
                q.emplace(l[u]);
            }
            if (r[u]) {
                dep[r[u]] = dep[u] + 1;
                q.emplace(r[u]);
            }
        }
        cout << (n - h) << "\n";
    }
}