Codeforces Round 1083 (Div. 2)——CF-2205-D. Simons and Beating Peaks（笛卡尔树）

题目大意

题目描述

定义一个长度为 $m$ 的数组 $b$ 是“好的”，当且仅当不存在任何索引 $i$ （ $1 < i < m$ ）满足 $b_i = \max(\{b_{i-1}, b_i, b_{i+1}\})$ 。

给定一个长度为 $n$ 的排列 $a$ 。如果数组不是“好的”，你可以反复执行以下操作：
选择一个满足 $a_i = \max(\{a_{i-1}, a_i, a_{i+1}\})$ 的索引 $i$ （ $1 < i < n$ ）。然后，你可以从数组中删除 $a_{i-1}$ 或 $a_{i+1}$ 。删除后，数组的左右两部分会重新拼接在一起。

求出使初始排列 $a$ 变为“好的”所需的最小操作次数。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 5 \cdot 10^4$ ），表示测试用例的数量。

对于每个测试用例：
第一行包含一个整数 $n$ （ $3 \le n \le 5 \cdot 10^5$ ），表示排列的长度。
第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le n$ ），表示初始的排列。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数，表示使数组变为“好的”所需的最小操作次数。

样例

输入

5
3
1 2 3
5
4 1 3 2 5
6
4 5 3 6 2 1
7
6 5 1 7 4 2 3
15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6

输出

样例解释

在第一组测试用例中，数组初始时已经是“好的”，因此不能执行任何操作，答案为 $0$ 。

在第二组测试用例中，可以进行如下操作：
选择索引 $3$ ，此时满足 $a_3 = \max(\{a_2, a_3, a_4\})$ （即 $3 = \max(\{1, 3, 2\})$ ）。接着从数组中移除 $a_2$ （元素 $1$ ）。数组变为 $[4, 3, 2, 5]$ 。
此时数组已经是“好的”，因此答案为 $1$ 。

在第三组测试用例中，可以进行如下操作：
选择索引 $2$ 。从数组中移除 $a_1$ 。数组变为 $[5, 3, 6, 2, 1]$ 。
选择索引 $3$ 。从数组中移除 $a_2$ 。数组变为 $[5, 6, 2, 1]$ 。
选择索引 $2$ 。从数组中移除 $a_1$ 。数组变为 $[6, 2, 1]$ 。
通过上述 $3$ 次操作，数组变为“好的”。

思路讲解

官方解法是这个笛卡尔树，不过我不太会这个东西，我们来看看其他做法吧。

https://www.luogu.com.cn/article/h4sddubz

这个 luogu 题解抓住了最大值一定不会被删除这个特性。（并不是删除最大值不优秀，而是重新阅读题面，你会发现）

luogu 题解递归式求解做法（我感觉挺好的）

题解：CF2205D Simons and Beating Peaks
注意到，数组的最大值必须置于两端。否则，我们必须将其左侧或右侧的所有元素全部删除，然后得到一个新的子数组。每次操作都会导致区间的缩小，因而可以递归求解。
具体地，对于区间 $[l, r]$ ，如果 $a_x = \max_{l \le i \le r} a_i$ ，那么我们有两种选择：

删去下标在 $l \sim x - 1$ 内的所有元素，区间缩小为 $[x + 1, r]$ 。
删去下标在 $x + 1 \sim r$ 内的所有元素，区间缩小为 $[l, x - 1]$ 。
因此，递推式为：

f_{l, r} = \min(r - x + f_{l, x - 1}, x - l + f_{x + 1, r})

如果暴力求解区间最大值，那么平均复杂度为 $O(n \log n)$ ，但若原数组单调，则会被卡成 $O(n^2)$ 。
故考虑用 ST 表维护区间最大值，递归过程可优化至 $O(n)$ 。
时间复杂度为 $O(\sum n \log n)$ ，瓶颈在 ST 表的初始化。

#include <bits/stdc++.h>
using namespace std;
int t, n, a[500001], pos[500001], st[500001][19];
int query(int l, int r) {
    int j = __lg(r - l + 1);
    return max(st[l][j], st[r-(1<<j)+1][j]);
}
int solve(int l, int r) {
    if (r - l <= 1) return 0;
    int x = pos[query(l,r)];
    return min(r - x + solve(l, x - 1), x - l + solve(x + 1, r));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            pos[a[i]] = i;
        }
        for (int i = 1; i <= n; i++) st[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++) 
                st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        cout << solve(1, n) << '\n';
    }
    return 0;
}

笛卡尔树

引入

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 $(k, w)$ 构成。要求 $k$ 满足二叉搜索树（BST）的性质，而 $w$ 满足堆的性质。如果笛卡尔树的 $k, w$ 键值确定，且 $k$ 互不相同， $w$ 也互不相同，那么这棵笛卡尔树的结构是唯一的。如下图：

（图源自维基百科）
上面这棵笛卡尔树相当于把数组元素值当作键值 $w$ ，而把数组下标当作键值 $k$ 。可以发现，这棵树的键值 $k$ 满足 BST 的性质，而键值 $w$ 满足小根堆的性质。同时根据二叉搜索树的性质，可以发现这种特殊的笛卡尔树满足一棵子树内的下标是一个连续区间。
竞赛中使用笛卡尔树时，常用数组下标作为二元组的键值 $k$ ，数组下标 $k$ 满足 BST 性质。
下文使用 $k, w$ 时，默认 $k$ 满足 BST 性质， $w$ 满足堆的性质。

单调栈构建笛卡尔树

过程

我们考虑将元素按 $k$ 升序依次插入到当前的笛卡尔树中。
对于一棵笛卡尔树，定义「右链」为从根节点开始一直走右儿子，走到叶节点形成的链。则插入节点后，这个节点一定在右链上。因为是按照满足 BST 性质的 $k$ 升序插入，那么这个新插入的节点必然在树的最右端。这个节点不可能是一个左儿子，也没有右儿子。
于是我们执行这样一个过程，从下往上比较右链节点与当前节点 $u$ 的 $w$ ，如果找到了一个右链上的节点 $x$ 满足 $w_x < w_u$ ，就把 $u$ 接到 $x$ 的右儿子上，而 $x$ 原本的右子树就变成 $u$ 的左子树。
图中红框部分就是我们始终维护的右链：

显然每个数最多进出右链一次（或者说每个点在右链中存在的是一段连续的时间）。这个过程可以用单调栈维护，栈中维护当前笛卡尔树的右链上的节点。一个点不在右链上了就把它弹掉。这样每个点最多进出一次，复杂度 $O(n)$ 。

笛卡尔树与 Treap

实际上，Treap 是笛卡尔树的一种，只不过 Treap 中 $w$ 的值完全随机。Treap 有线性的构建算法，如果提前将键值 $k$ 排好序，是可以使用上述单调栈算法完成构建过程的，只不过很少会这么用。

C++ 实现

// stk 维护笛卡尔树中节点对应到序列中的下标
for (int i = 1; i <= n; i++) {
  int k = top;  // top 表示操作前的栈顶，k 表示当前栈顶
  while (k > 0 && w[stk[k]] > w[i]) k--;  // 维护右链上的节点
  if (k) rs[stk[k]] = i;  // 栈顶元素.右儿子 := 当前元素
  if (k < top) ls[i] = stk[k + 1];  // 当前元素.左儿子 := 上一个被弹出的元素
  stk[++k] = i;                     // 当前元素入栈
  top = k;
}

AI 总结的笛卡尔树式解法

一、笛卡尔树是什么

笛卡尔树（Cartesian Tree）是一种由序列构造出的二叉树，同时满足两个性质：

堆性质：每个子树的根节点是该子树中所有元素的最大值（大根笛卡尔树）或最小值（小根笛卡尔树）。
中序遍历性质：对树做中序遍历，得到的恰好是原序列。

构造方式（以大根笛卡尔树为例）

对于序列 $a_1, a_2, \ldots, a_n$ ：

根：整个序列的最大值 $a_p$ 。
左子树：由 $a_1, \ldots, a_{p-1}$ （最大值左边的部分）递归构造。
右子树：由 $a_{p+1}, \ldots, a_n$ （最大值右边的部分）递归构造。
以题目的样例 [4, 5, 3, 6, 2, 1] 为例：

          6(pos=4)
         / \\
   5(pos=2)  2(pos=5)
      / \\       \\
4(pos=1) 3(pos=3) 1(pos=6)

根是 6（全局最大），位置 4
左半 [4, 5, 3] 的最大值是 5（位置 2），成为左子树根
右半 [2, 1] 的最大值是 2（位置 5），成为右子树根
依此递归
核心直觉：笛卡尔树刻画了"每个区间的最大值把该区间分成左右两半"这一递归分治结构。

二、为什么这道题和笛卡尔树有关

第一步：理解"cool"数组的结构

“cool"数组要求没有内部峰值（即没有任何内部元素同时大于左右邻居）。由于元素互不相同，一个没有内部峰值的数组只能是先递减、再递增的"V 形”：

a_{i_1} > a_{i_2} > \cdots > a_{i_k} < a_{i_{k+1}} < \cdots < a_{i_m}

（递减或递增部分可以为空，即纯递增、纯递减也合法。）
如果序列中间出现了一个"先升后降"的拐点，那个拐点就是一个峰值，违反 cool 条件。

第二步：全局最大值 $n$ 必定保留且在端点

每次操作是"选一个峰 $a_i$ ，删掉 $a_{i-1}$ 或 $a_{i+1}$ "。被删除的只能是峰的邻居，而不是峰本身。全局最大值 $n$ 永远不可能是某个峰的邻居（因为没有比它更大的元素），所以 $n$ 永远不会被删除。
既然 $n$ 一定留在最终数组中，而最终数组是 V 形的，那么 $n$ 作为最大值如果出现在内部，它一定是峰值——矛盾。所以 $n$ 必须在最终数组的左端点或右端点。

第三步：递归结构 = 笛卡尔树

假设 $n$ 在位置 $p$ ：

$n$ 放左端点： $p$ 左边的所有元素全部删掉，只保留 $n$ + 右半部分的某个 V 形子序列。
$n$ 放右端点： $p$ 右边的所有元素全部删掉，只保留左半部分的某个 V 形子序列 + $n$ 。
无论哪种情况，问题递归到了 $n$ 的一侧。而那一侧的最大值（笛卡尔树对应子树的根）面临完全相同的约束——它也必须在该子问题最终数组的端点，否则它也是峰值。
这恰好是笛卡尔树的递归结构：

f(v) = 1 + \max\big(f(\text{左子树}),\; f(\text{右子树})\big)

其中 $f(v)$ 是以 $v$ 为根的子树中，能保留的最多元素数（即最长合法 V 形子序列的长度）。

基础情况： $f(\text{叶子}) = 1$ ， $f(\text{空}) = 0$ 。
每一步我们保留当前根（+1），然后在左右子树中选更优的一侧递归下去。
$f(\text{root})$ 就是笛卡尔树的高度（从根到叶的最长路径上的节点数）。

第四步：答案

\boxed{\text{答案} = n - h}

其中 $h$ 是大根笛卡尔树的高度。

验证样例

以 [4, 5, 3, 6, 2, 1] 为例，笛卡尔树如上图所示：

$f(4) = 1$ ， $f(3) = 1$ ， $f(1) = 1$
$f(5) = 1 + \max(1, 1) = 2$
$f(2) = 1 + \max(0, 1) = 2$
$f(6) = 1 + \max(2, 2) = 3$
答案 $= 6 - 3 = 3$ 。对应最优方案保留 [6, 2, 1]（ $6 > 2 > 1$ ，纯递减，合法 V 形）。

为什么可以拼接？

你可能会问：把根 $v$ 接到子树的 V 形子序列前面/后面，结果还是 V 形吗？
是的。因为 $v$ 是子树中的最大值，一定大于子序列的所有元素：

$v$ 放左端： $v$ 接上右子树的 V 形 $[d_1, \ldots, d_k, u_1, \ldots, u_m]$ ，得到 $v > d_1 > \cdots > d_k < u_1 < \cdots < u_m$ ，仍是 V 形。
$v$ 放右端：对称，左子树的 V 形后面接 $v$ ，增长的部分末尾加上了更大的 $v$ ，仍是 V 形。

总结

概念	对应关系
笛卡尔树的根	区间最大值，必须放在最终数组端点
选左/右子树	决定保留最大值的哪一侧
笛卡尔树高度 $h$	最多能保留的元素数
答案 $n - h$	最少删除次数
笛卡尔树精确刻画了"每一级的最大值都必须在端点"这一层层递归的约束，这就是它与本题的本质联系。

我们最终采用的呢，是递归式求解做法啊，也就是分治做法，配合使用的那个ST表。

这个是利用了最大值一定不会被删除的这个特性，而且还利用了一个特性，就是只要这个最大值它不在L或者不在R，一定要把L旁边的或者R旁边的全部给删掉。

auto solve=[&](auto && self,ll l,ll r) -> ll {
    if (l>=r) {
        return 0;
    }
    ll mx_i=st.query(l,r);
    ll tmp1=self(self,l,mx_i-1);
    ll tmp2=self(self,mx_i+1,r);
    ll res=min(tmp1 + r-mx_i ,tmp2 + mx_i-l);
    return res;
};

AC代码

AC
https://codeforces.com/contest/2205/submission/365029208

源代码

/**
 * Problem: D. Simons and Beating Peaks
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/D
 * Created: 2026-03-02 00:06:04
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

/*
 *2025/12/10 AC https://codeforces.com/contest/2175/submission/352780861
 *2025/3/2 实现了这个 op 函数的传入（可以传入一个 lambda 函数）
 *AC https://codeforces.com/contest/2205/submission/365029208
 *
 */
template<class T,class F>
struct ST {
    ll N;
    vector<vector<T>> dp;
    F op;
    // static T op(const T &a,const T &b) {
    //     return max(a,b);
    // }
    ST(ll N,const vector<T> &a,F fun):N(N),dp(__lg(N)+1,vector<T>(N+5)),op(fun) {
        for (int i=1;i<=N;++i) {
            dp[0][i]=a[i];
        }
        for(int lay=1;lay<=__lg(N);++lay) {
            for(int i=1;i<=N-(1<<(lay-1));++i) {
                dp[lay][i]=op(dp[lay-1][i] , dp[lay-1][i+(1<<(lay-1))]);
            }
        }
    }
    T query(ll l,ll r) {
        ll lay=__lg(r-l+1);
        return op(dp[lay][l],dp[lay][r-(1<<lay)+1]);
    }
};


void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    auto max_i=[&](const ll &ai,const ll &bi) -> ll{
        if (A[ai]>=A[bi]) {
            return ai;
        }
        return bi;
    };
    vector<ll> vec_idx(N+2);
    for (int i=1;i<=N;++i) {
        vec_idx[i]=i;
    }
    ST<ll,decltype(max_i)> st(N,vec_idx,max_i);
    // 这个其实就是借用了这个最大值要么就必须靠在左边，要么靠在右边
    // 因为最大值实际上是不能删的
    auto solve=[&](auto && self,ll l,ll r) -> ll {
        if (l>=r) {
            return 0;
        }
        ll mx_i=st.query(l,r);
        ll tmp1=self(self,l,mx_i-1);
        ll tmp2=self(self,mx_i+1,r);
        ll res=min(tmp1 + r-mx_i ,tmp2 + mx_i-l);
        return res;
    };
    ll ans=solve(solve,1,N);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/365029208


1
7
6 5 1 7 4 2 3


*/

心路历程（WA，TLE，MLE……）

C++ 14下，因为必须传入模板参数，嗯，可以这样子写其模板类型。

1	ST<ll,decltype(max_i)> st(N,vec_idx,max_i);

嗯，我们可以看到，嗯，这里应该是减L，不应该是减1。

auto solve=[&](auto && self,ll l,ll r) -> ll {
    if (l>=r) {
        return 0;
    }
    ll mx_i=st.query(l,r);
    ll tmp1=self(self,l,mx_i-1);
    ll tmp2=self(self,mx_i+1,r);
    ll res=min(tmp1 + r-mx_i ,tmp2 + mx_i-l);
    return res;
};