题目链接: 核心考点: [[思维]]

D. Rae Taylor and Trees (easy version)

时间限制：每测试点3秒
内存限制：每测试点256 MB

问题描述

"想想看，一个平民竟然会坐在我旁边。知道自己的位置！"
— Claire François

这是问题的简单版本。简单版本和困难版本之间的唯一区别是，困难版本要求您构造一个满足条件的树的示例。

作为一名地球法师，Rae已经掌握了生长树木的法术！但是Manaria夸口说她能种植一种更令人印象深刻的树种。Rae记得最稀有的树种可以使用由特定排列表示的公式来生长——请帮助她构造它！

您将得到一个长度为 $n$ 的排列$^*$ $p$。

确定是否存在一个具有 $n$ 个顶点（标记为 $1,2,\ldots,n$）的无向树，满足以下条件：

对于任意两个由边连接的顶点 $u$ 和 $v$ ($1 \leq u < v \leq n$)，$u$ 在 $p$ 中出现在 $v$ 之前。

$^*$长度为 $n$ 的排列是一个数组，它包含从 $1$ 到 $n$ 的每个整数恰好一次，顺序任意。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 2 \cdot 10^5$)。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$)。保证所有的 $p_i$ 都是不同的。

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

输出格式

对于每个测试用例，如果存在满足给定条件的树，输出一行"Yes"；否则输出"No"。

答案可以以任何大小写形式输出。例如，字符串"yEs"、"yes"、"YES"和"yeS"都会被识别为"Yes"。

样例输入

9
6
1 3 4 5 2 6
4
3 4 1 2
5
4 3 5 1 2
4
1 2 3 4
7
4 3 5 7 6 2 1
6
2 4 6 1 3 5
3
2 1 3
4
2 4 1 3
6
4 2 6 5 1 3

样例输出

Yes
No
No
Yes
No
Yes
Yes
Yes
Yes

样例说明

在第一个样例中，我们可以构造具有以下边的树：

$\{3,1\}$, $\{4,1\}$, $\{6,5\}$, $\{6,2\}$, $\{6,1\}$。

那么我们有：

• $1 < 3$，且 $1$ 在 $p$ 中出现在 $3$ 之前
• $1 < 4$，且 $1$ 在 $p$ 中出现在 $4$ 之前
• $5 < 6$，且 $5$ 在 $p$ 中出现在 $6$ 之前
• $2 < 6$，且 $2$ 在 $p$ 中出现在 $6$ 之前
• $1 < 6$，且 $1$ 在 $p$ 中出现在 $6$ 之前

在第二个样例中，可以证明不存在满足给定约束的树。

本题的理解

这道题（D. Rae Taylor and Trees - Easy Version）是一个非常典型的思维转化题。它考察的不是复杂的图论算法，而是你对“连通性”本质的理解。

1. 题目核心翻译

我们要用给定的排列 $p$ 里的 $n$ 个点造一棵树。

边的规则： 如果你想连接点 $u$ 和点 $v$（假设 $u < v$），那么 $u$ 必须在排列 $p$ 中出现在 $v$ 的前面。

通俗理解：

这相当于在这个数组上，如果左边的数比右边的数小，你就可以在这两点之间连一条线。

现在问：能不能选出 $n-1$ 条线，把所有点连成一个整体（树）？

---

2. 核心思考路径

第一步：把“造树”转化为“连通性”

题目问的是“是否存在一棵树”。

树的最基本性质是连通。

如果我们能发现某种情况会导致图彻底断开，那肯定造不出树。

第二步：寻找“切断”图的条件

想象我们拿一把刀，在排列数组的某个位置 $i$ 砍一刀，把数组分为左边 (Prefix) 和 右边 (Suffix) 两部分。

• 左边部分： $p_1, p_2, \dots, p_i$

• 右边部分： $p_{i+1}, \dots, p_n$

为了让整个图连通，必须至少有一条边能跨过这个切口，连接左边的一个点和右边的一个点。

根据题目规则，跨越切口的边 $(u, v)$ 必须满足：

1. $u$ 在左边，$v$ 在右边。

2. $u$ 必须出现在 $v$ 前面（天然满足，因为左边都在右边前面）。

3. $u$ 必须小于 $v$ ($u < v$)。

关键点来了：

如果在某个切口处，左边所有的数都比右边所有的数大，会发生什么？

• 那左边随便挑一个 $u$，右边随便挑一个 $v$，永远都是 $u > v$。

• 这违反了连边的条件 ($u < v$)。

• 结论： 这种情况下，没有任何一条边能跨越这个切口。图被切断了！输出 No。

第三步：量化条件

要判断“左边所有的数都比右边所有的数大”，我们不需要比较每一对数。

只需要比较：

左边的最小值 (Prefix Min) > 右边的最大值 (Suffix Max)

如果这个不等式成立，说明左边连“最菜”的数都比右边“最强”的数大，那彻底没戏了。

第四步：反过来想（充分性）

如果对于每一个切口，都能找到左边的某个数比右边的某个数小（即 Prefix Min < Suffix Max），是不是就一定能造出树？

• 是的。这保证了每个切口都有“桥梁”。对于简单版题目，我们只要找到这个破坏连通性的唯一死穴即可。

---

3. 算法逻辑

1. 预处理右边的最大值： 创建一个数组 sufMax，其中 sufMax[i] 表示从 $p[i]$ 到 $p[n-1]$ 这一段里的最大值。

2. 遍历左边： 从左到右遍历数组，维护一个变量 preMin 表示当前左边的最小值。

3. 检查每一个切口： 对于每个位置 $i$（从 $0$ 到 $n-2$）：

   • 检查是否 preMin > sufMax[i+1]。

   • 如果出现了这种情况，说明在这个位置切开后，左边全部大于右边，图断开了 $\to$ 输出 No。

4. 如果遍历完所有切口都没问题 $\to$ 输出 Yes。

---

4. 样例验证

样例 2： 3 4 1 2

• 切口 1（3 | 4 1 2）： 左最小 3，右最大 4。$3 < 4$，OK。

• 切口 2（3 4 | 1 2）： 左最小 3，右最大 2。$3 > 2$，炸了！

  • 左边是 $\{3, 4\}$，右边是 $\{1, 2\}$。左边任意数都比右边大，没法连线。

  • 输出 No。

样例 5： 4 3 5 7 6 2 1

• ...

• 切到 4 3 5 7 6 | 2 1 时：

  • 左边最小是 3。

  • 右边最大是 2。

  • $3 > 2$，断开了。

  • 输出 No。

样例 6： 2 4 6 1 3 5

• 无论怎么切，左边的最小值（比如 1 或 2）总是小于右边的最大值（比如 5 或 6）。

• 输出 Yes。

---

5. 代码参考

C++

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

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    // 1. 预处理后缀最大值
    // sufMax[i] 代表 p[i...n-1] 范围内的最大值
    vector<int> sufMax(n);
    sufMax[n - 1] = p[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        sufMax[i] = max(sufMax[i + 1], p[i]);
    }

    int preMin = p[0];
    // 2. 遍历每一个可能的切口
    // i 表示切口在 p[i] 和 p[i+1] 之间
    for (int i = 0; i < n - 1; i++) {
        preMin = min(preMin, p[i]);

        // 核心判断：如果左边的最小值 > 右边的最大值，则断开
        if (preMin > sufMax[i + 1]) {
            cout << "No" << endl;
            return;
        }
    }

    cout << "Yes" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

总结

这道题教会我们一种分析连通性问题的视角：切割法。

当题目对连边有严格的大小/顺序限制时，去寻找是否存在一个“断层”，使得两边的元素因为规则限制而无法产生任何连接。如果有断层，就是 No；否则就是 Yes。

我感觉我真是走不长了

哪怕是现在 Codeforces 红名（Grandmaster）的大佬，在他们还是新手或者中间阶段时，也无数次有过这种“我看题解觉得像弱智题，但我自己死活想不出来”的崩溃时刻。

你并不是“笨”，你只是大脑里的“模型库”缺了这一块拼图。

这就好比你从来没见过“剪刀”，然后让你去把一张纸分开。你可能会想着用手撕、用牙咬、用水泡烂，最后有人拿出一把剪刀“咔嚓”一下剪开了。你恍然大悟的同时肯定会很懊恼：“我怎么没想到有两个铁片交叉一下就能分开纸呢？”

因为你没见过剪刀。

这道题考察的不是你熟悉的 BFS、DFS 或者贪心，它考察的是一种“破坏性思维”。

我来帮你拆解一下，这种思维到底是怎么运作的，以及如何刻意练习。

---

一、 你的思维 vs 出题人的思维

1. 你的思维路径（建设者思维）

拿到题，你的大脑在疯狂运转：

• “我要怎么连线？”

• “是不是小的连大的？”

• “是不是用贪心，每个点找最近的？”

• “我要把树造出来！”

这种思维叫“建设者思维” (Constructive Thinking)。 90% 的题目都是这样的，所以你这种直觉通常是有用的。

2. 这道题需要的思维（破坏者思维）

这道题是 Yes/No 题。对于这类题，高手的直觉通常是反过来的：

• “别光想着怎么造树了，什么情况下我绝对造不出来？”

• “什么情况下，这个图会断成两半？”

• “敌人在哪里切一刀，我就死定了？”

这种思维叫“瓶颈思维” (Bottleneck/Cut Thinking)。

为什么你没想到？

因为我们在学校、在基础算法训练里，学的全是“怎么做加法”（怎么连通、怎么求和）。很少有人教我们“怎么做减法”（怎么切断、怎么破坏）。

---

二、 如何培养这种“破坏性直觉”？

下次遇到这种“是否存在”、“能不能”的题目，强迫自己进行以下三个思维体操：

体操 1：寻找“马其诺防线” ( The Cut )

如果是线性结构（数组、序列），最容易出问题的地方永远是“把数组切成两半”的地方。

• 自我提问： “如果我在中间切一刀，左边和右边还能联系上吗？”

• 应用到本题： 切一刀 $\to$ 左边要连右边 $\to$ 必须 $u < v$。如果左边全是大个子，右边全是小个子，那完蛋了，联系不上。 $\to$ 破案了。

体操 2：极端反例构造法

不要去想 $N=100$ 的随机数据，去想最恶心的数据。

• 自我提问： “出题人想让我死，他会给我什么样的数据？”

• 尝试：

  • 完全倒序？5 4 3 2 1。左边全是大的，右边全是小的。诶？这好像就是连不上的情况！

  • 那我稍微改一下，4 5 1 2 3。切在 5 和 1 中间，左边最小是 4，右边最大是 3。又连不上了！

• 顿悟： 只要你开始尝试“搞破坏”，你就会发现“左大右小”这个规律。

体操 3：关注“必要条件”

建设者思维找的是“充分条件”（找到一种连法就能赢）。

破坏者思维找的是“必要条件”（只要缺了这个就得死）。

• 连通图的必要条件是什么？是任意两部分之间必须有边。

• 这一条往往就是解题的钥匙。

---

三、 具体的训练计划（止哭药方）

我知道你现在很急，觉得智商被碾压。请按照这个步骤来，一个月后你会不一样的：

1. 建立“失败档案”

   不要只是 AC 了就跑。把你今天这道题，打上标签：Tag: 连通性、Tag: 破坏性思维、Tag: 瓶颈。

   在你的笔记里写下：“这道题我死在只想怎么连边，没想怎么切断。”

2. 做“构造/思维”专项训练

   在 Codeforces 上，专门筛选 constructive algorithms (构造) 和 graphs (图论) 难度在 1200-1500 分的题目。

   • 做题时，先花 5 分钟想：怎么证明它是 No？

   • 如果想不出来，再想怎么构造 Yes。

3. 学会“左右互搏”

   下次看到序列题，下意识地问自己：

   • Prefix（前缀）有什么性质？

   • Suffix（后缀）有什么性质？

   • Prefix Min/Max 和 Suffix Min/Max 有什么关系？

   • 这道题其实就是 PreMin 和 SufMax 的博弈。 这种“前缀最值 vs 后缀最值”的模型，在算法题里出现了至少 100 次！你这次记住了，下次就能秒杀。

给你的安慰

这道题归类为 Easy Version，但其实它的思维难度并不低，它属于那种“窗户纸”题目——捅破了觉得很透亮，捅不破就是一堵墙。

你今天撞墙了，这是好事。因为你撞到了一个新的知识边界。

现在，把眼泪擦一擦。你今天学会了“剪刀”的用法。下次再遇到一张纸，你就是那个能把它剪开的人了。

要不要我再给你出一道类似的、考察“破坏性思维/瓶颈”的简单题，让你找回一点自信？

💡 核心直觉 (一句话总结)

这种构造题学会找反例

🚫 我的误区 (Fail Log)

• 思路错误: 这道题我死在只想怎么连边，没想怎么切断
• 实现错误:
• 数据范围:

✅ 正解思路

🧠 举一反三 (Pattern)

• 下次看到 "YES NO" -> 想到 是否有判断NO 然后直接YES

---

💻 代码

```cpp // Problem: CF 2171 D // Contest: Codeforces - Codeforces Round 1065 (Div. 3) // URL: https://codeforces.com/contest/2171/problem/D // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)

include

using namespace std; typedef long long LL; typedef pair PII; const int N=1e6+7; const int mod=1e9+7;

void solve(){ int n; cin>>n; vector a(n+1); for(int i=1;i<=n;i++){ cin>>a[i]; } vector pre(n+2,1e9),suf(n+2,0); for(int i=1;i<=n;i++){ pre[i]=min(pre[i-1],a[i]); } for(int i=n;i>0;i--){ suf[i]=max(a[i],suf[i+1]); }

for(int i=2;i<=n;i++){
    if(pre[i-1]>suf[i]){
        printf("No\n");
        return ;
    }
}
printf("Yes\n");
return ;

}

int main(){ int t; cin>>t; while(t--){ solve(); } return 0; } ````