今天想认真复盘一下 Educational Codeforces Round 187 (Rated for Div.2)。这轮我是赛后 virtual 补的，前四题恰好把“滑动窗口、交换排序、排列构造、树形统计”这四类 CF 里特别常见的考点串了一遍。A 题和 B 题都不难，但 B 题稍微不留神就会往逆序对上想；C 题属于“想通上界就完全白给”的构造；D 题的主要坑在根节点的选取上。下面按我实际写题顺序，把每道题从读题到 AC 的完整思考链写出来，代码统一用 C++17。
1. 这轮 A-D 到底在考什么：四道题的知识点与难度曲线
先说整体感受。这轮的难度分布并不是“线性上升”，而是中间突然有个认知门槛：A 题几乎是签到，B 题很多人会被带偏，C 题是个典型的构造，D 题则是树形 DFS 的变体。如果只看题解会觉得都很常规，但赛场上从 B 到 C 的切换很容易让人心态不稳。
我按自己补题时的顺序把 A-D 拆成了四个独立模块：
- A 题：数组 + 最值 + 最短子段，核心是滑动窗口/双指针的取舍；
- B 题：01 串交换排序，核心是“任意交换”和“相邻交换”两种模型的区别；
- C 题：排列构造，核心是先证明答案上界，再顺着上界去构造；
- D 题：树上关键点连接，核心是把问题转化成“最小连通点集有多少个点”。
这四题放在一起很适合 mid 到 high 1400 分段的选手练手，因为它考的不是冷门算法，而是“能不能一眼选对模型”。A 题如果一上来写二分和前缀最值，也能过，但会明显变慢；B 题如果下意识当成逆序对做，就会在当前这个模型里得到错误答案；C 题没有先证明上界，很容易构造出一半就卡住；D 题如果根随便选一个非关键点，样例可能都过不了。
我补题时的时间大概是这样：A 题看题加实现用了 5 分钟，B 题因为一开始确实往逆序对上想了一下，绕了 15 分钟，C 题证明完上界之后 10 分钟写完，D 题第一次提交 WA 在一个边界样例上，最后改成“用关键点当根”才过。这个时间线其实很典型，下面每道题的坑我都会单独指出来。
2. A 题：包含全局最小值和最大值的最短子段，扫一遍就够了
2.1 题意与第一反应
题意很直接：给定长度为 n 的数组 a，找一个最短的连续子数组，使得这个子数组里同时包含整个数组的最小值 mn 和最大值 mx，输出最短长度。
我第一反应是“这题是不是要二分长度”？因为“最短长度”听起来很二分：check(mid) 是否存在长度 mid 的子段同时含有 mn 和 mx。然后维护前缀中最值位置或者用滑动窗口判断。这样确实能做，但复杂度会变成 O(n log n)，作为 A 题小题大做了。
实际上这个问题有一个更本质的性质：如果某个子段 [l, r] 同时包含 mn 和 mx，那么它内部一定有一个位置是 mn，另一个位置是 mx。换句话说，区间长度至少是从其中一个极值到另一个极值的距离加一。所以最优解一定可以表示成“从某个极值位置到另一个极值位置的一段”。
2.2 为什么枚举右端点能覆盖所有最优解
我最后采用的方法是线性扫描，同时维护两个变量：
- lastMn：最后一次出现 mn 的下标；
- lastMx：最后一次出现 mx 的下标。
从左往右扫描到 i 时，如果 a[i] 等于 mn，那么以 i 为右端点、且同时包含两个极值的最短合法区间，左端点必然是 lastMx，长度为 i - lastMx + 1；同理，如果 a[i] 等于 mx，就用 i - lastMn + 1 更新答案。
为什么这样不会漏？因为每个最优区间都有一个右端点。当扫描到这个右端点时，如果它恰好是其中一个极值，另一个极值在区间里最后一次出现的位置，一定就是当前维护的 lastMn 或 lastMx。此时用它们计算出的长度，不会比真正的最优区间更长。容忍一下多更新几次，答案只会更小不会漏掉。
还有一种想法是“枚举左端点，找右边最近的另一个极值”，方向完全反过来也可以。但枚举右端点的好处是状态少，不需要预处理 next 数组。
2.3 完整代码与复杂度
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; vector<int> a(n); int mn = INT_MAX, mx = INT_MIN; for (int i = 0; i < n; i++) { cin >> a[i]; mn = min(mn, a[i]); mx = max(mx, a[i]); } if (mn == mx) { cout << 1 << '\n'; continue; } int ans = n; int lastMn = -1, lastMx = -1; for (int i = 0; i < n; i++) { if (a[i] == mn) { lastMn = i; if (lastMx != -1) ans = min(ans, i - lastMx + 1); } if (a[i] == mx) { lastMx = i; if (lastMn != -1) ans = min(ans, i - lastMn + 1); } } cout << ans << '\n'; } return 0; }时间复杂度 O(n)，空间复杂度 O(n)。其实可以只读两个极值再扫一遍，但读入时必须至少存一次数组，所以 O(n) 空间无所谓。
2.4 边界情况
最容易翻车的是 mn == mx，也就是数组中所有数都一样。这时最短合法子段长度当然是 1，直接特判，否则 lastMn 和 lastMx 会同时更新，答案会被算成 1 之外的其他值吗？其实也会得到 1，但特判更稳，少一点边界讨论。
另外一个细节是：不要用if (a[i] == mn)和else if (a[i] == mx)。如果数组长度为 1，或者 mn == mx，会出问题。用两个独立的 if 更安全，反正一个数不可能同时等于两个不同极值。
3. B 题：01 串任意交换的最小次数，答案不是逆序对数
3.1 题意
给一个 01 串 s，每次操作可以任选一对位置 i < j，要求 s[i] = '1' 且 s[j] = '0'，然后把这两个字符交换。问最少多少次操作，可以让所有 '0' 都排在所有 '1' 前面。
注意，这里的关键是“任意交换”，不是“交换相邻位置”。我看到不少人在这个题上会条件反射想到逆序对，因为“把 01 串排成 00...11”和冒泡排序模型太像了。但这题的每次操作是一次交换两个位置，完全可以一次修好两个错位字符。
3.2 关键观察：错位成对，一次交换修两个
假设原串长度为 n，其中有 c0 个 '0'。最终目标串是唯一的：前 c0 个字符是 '0'，后面全是 '1'，因为 0 和 1 的总数量不会因为交换改变。
把原串 s 和目标串 target 逐位比较，统计有多少个位置不同，记为 diff。由于两个串的 '0' 数量相同，所以不同的位置一定是“原串是 1、目标是 0”和“原串是 0、目标是 1”两种位置成对出现，diff 一定是偶数。
一次合法操作交换一个 '1' 和一个 '0'，如果选的恰好是这两种错位字符，交换后这两个位置都归位了，diff 直接减少 2。最理想情况下，每次都选到这样的配对，所以下界是 diff / 2。
这个下界可以达到，因为只要还存在错位，就一定存在一个左边的错位 '1' 和一个右边的错位 '0'，选它们交换即可。所以答案就是 diff / 2。
3.3 和相邻交换的差别
相邻交换模型下，把 01 串变成全 0 在前全 1 在后，答案等于逆序对数量，也就是每个 '1' 后面 '0' 的个数之和。比如 "1100" 的逆序对数是 4，相邻交换需要 4 次。
但在任意交换模型下，"1100" 的目标是 "0011"，逐位比较：
- 位置 1：1 vs 0，不同
- 位置 2：1 vs 0，不同
- 位置 3：0 vs 1，不同
- 位置 4：0 vs 1，不同
diff = 4，答案 = 2。操作可以这样完成：先交换位置 1 的 '1' 和位置 4 的 '0'，得到 "0101"；再交换位置 2 的 '1' 和位置 3 的 '0'，得到 "0011"。
所以“任意交换”和“相邻交换”从模型上就是两回事。做题时如果看到“选择任意两个位置交换”，先别急着套逆序对；如果看到“交换相邻元素”，再考虑逆序对。
3.4 代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; string s; cin >> n >> s; int cnt0 = 0; for (char c : s) { if (c == '0') cnt0++; } int diff = 0; for (int i = 0; i < n; i++) { char need = (i < cnt0 ? '0' : '1'); if (s[i] != need) diff++; } cout << diff / 2 << '\n'; } return 0; }补充一个容易忽略的点：构造 target 时不一定真的生成一个新字符串，直接比较s[i]和(i < cnt0 ? '0' : '1')就行。如果题目给的 n 很小当然无所谓，但这个习惯在大数据下能省一个串的内存和一次构建时间。
4. C 题：排列相邻差集合最大化的构造，先证明上界再谈做法
4.1 上界是 n-1
题意可以描述成：构造一个 1 到 n 的排列 p，使得所有相邻位置绝对差 |p[i] - p[i+1]| 的不同取值数量尽量多，输出任意一个达到最大值的排列。
首先想清楚答案最多是多少。两个数在 1 到 n 之间，差的绝对值最小是 1，最大是 n-1。所以所有相邻差最多只有 n-1 种不同取值。如果你想达到最大值，就必须让 1 到 n-1 这 n-1 个差值全部出现一次。
这个上界虽然简单，但它是整个题的基石。很多同学一上来直接随机排列去试，或者用 DFS 回溯构造，完全没必要。先证明上界，再顺势设计构造，题目会瞬间变简单。
4.2 构造：交替取两端
我们要让相邻差分别等于 n-1, n-2, n-3, ..., 1。最容易想到的排列就是从两端交替取数：
p = 1, n, 2, n-1, 3, n-2, ...
以 n = 6 为例：1, 6, 2, 5, 3, 4，相邻差分别是 5, 4, 3, 2, 1，完美覆盖 1 到 n-1。
为什么能覆盖？因为每次交替从剩余区间两端取值，两个数的距离正好等于当前剩余区间的长度。区间长度最开始是 n-1，每次取完两个端点后，剩余区间长度减少 1，所以产生的差值正好从 n-1 一直降到 1。
4.3 为什么证明上界之后构造就顺了
如果先证明上界，你就会知道目标不是“随便构造一个看起来花的排列”，而是“让差值恰好是 n-1, n-2, ..., 1”。这个目标直接指向双指针。
从一个空序列开始：
- 左边放 l = 1，右边放 r = n；
- 先放 l，l++；
- 如果 l <= r，放 r，r--；
- 重复直到所有数放完。
这种“从两头往中间夹”的模式在很多构造题里都出现过。它本质上是在保证相邻两个数之间的距离单调递减。
4.4 代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; int l = 1, r = n; vector<int> ans; while (l <= r) { ans.push_back(l++); if (l <= r) ans.push_back(r--); } for (int i = 0; i < n; i++) { cout << ans[i] << (i + 1 == n ? '\n' : ' '); } } return 0; }注意循环里push_back(l++)和push_back(r--)的顺序。如果先放右端点再放左端点，得到的差值顺序会变成小的开头，但不影响覆盖 1 到 n-1，不过实现时容易越界，所以写成上面的形式最稳。
4.5 一个小坑
n = 1 和 n = 2 需要额外确认。n = 1 时没有相邻差，排列就是 [1]，输出 1；n = 2 时排列 [1, 2] 或 [2, 1] 都只有一个差值 1。上面的双指针代码天然能处理这两种情况，因为 ans 的长度严格等于 n。构造题里这种极小的 n 经常让人在边界上翻车，建议每次写完构造都手动跑一遍 n=1、n=2、n=3、n=4。
5. D 题：树上关键点连通要补几个点，根选错会直接 WA
5.1 题意转化
这题大概是这样的模型：给一棵 n 个点的树，其中有 k 个点是“关键点”。每次操作可以额外“点亮”一个点，点亮后这个点也变成关键点。目标是让所有关键点（包括初始的和新点亮的）在树上构成一个连通点集。问最少要点亮多少个点。
换句话说，树上本来有一些点需要连通，但路径上可能缺中间点。因为树的边只能连接相邻点，如果两个关键点之间的路径上有一个点没有被点亮，那么这整段就不连通。所以答案等于“包含所有关键点的最小连通子图”的点数减去 k。
这个最小连通子图其实就是一个简化版的虚树：把不在任何关键点路径上的多余分支全砍掉，只保留对连通性必要的点和边。在一棵树上求它不需要建虚树，也不需要 LCA，直接用一次 DFS 统计每条边是否需要保留。
5.2 统计最小连通子图
任选一个点作为根，做一次 DFS，维护每个子树里有多少个关键点，记为 sz[u]。
对于一条边 u-v，其中 v 是 u 的儿子，如果 sz[v] > 0 且 sz[v] < k，说明删掉这条边后，关键点被分成了两边，两边都有关键点。为了让所有关键点连通，这条边必须被保留下来。
统计所有需要保留的边数 edges。一个由 edges 条边组成的连通子图，点数一定是 edges + 1。所以答案 = (edges + 1) - k。
5.3 为什么根必须是关键点
这是这题最大的坑。我第一次提交时随便拿了节点 1 当根，结果在“关键点不在同一棵子树”的样例上错了。
原因很简单：如果根不是关键点，那么根到某个关键点之间的路径可能实际上不属于最小连通子图，但在 DFS 统计时，这些边两侧也可能都有关键点。比如一条链 1-2-3，关键点是 2 和 3。如果拿 1 当根，DFS 从 1 走到 2，再走到 3，假设 sz[3] = 1，边 2-3 需要保留；再看边 1-2，它的子树（以 2 为根的子树）里有两个关键点，正好等于 k，所以不会被计入。此时 edges = 1，答案 = 1 + 1 - 2 = 0，但显然至少需要额外点亮 0 个点？其实这里关键点 2 和 3 本身通过边 2-3 连通，答案是 0。那么 1-2 这条边不保留是对的，答案正确。这不是坏例。
换一个例子：一条链 1-2-3，关键点是 1 和 3。如果拿 2 当根，根不是关键点。DFS 需要保留边 2-3（子树有关键点3），保留边 1-2（子树有关键点1），edges = 2，答案 = 2 + 1 - 2 = 1。但实际上关键点 1 和 3 之间的路径是 1-2-3，缺中间点 2，需要额外点亮 1 个点，答案确实是 1。这个例子里结果是对的。
那根选非关键点什么时候会错？考虑一个星形或分支结构：根是非关键点，且它上方并没有关键点，但它连接了两个关键点子树。比如树：根 r，r 的儿子 a 是关键点，r 的儿子 b 是关键点，且 r 本身不是关键点。如果拿 r 当根，两条边 r-a 和 r-b 的子树关键点数量都是 1，都 < k=2，且 >0，所以都会计入，edges=2，答案 = 2+1-2=1。而实际最小连通子图应该包含 a、b、r 三个点，确实需要点亮 r，答案也是1，又对。
那根非关键点会错的场景是：最小连通子图不包含根，但根的某条边两侧都有关键点。例如树：1 是根，1-2 是一条长链，2 是关键点；1 还连接 3，3 是关键点。链 1-2-3 是关键点 2 和 3，根 1 不在路径上。如果拿 1 当根，边 1-2 的子树关键点数量 = 2（2 和 3），正好等于 k，不计入；边 2-3 的子树关键点数量 = 1，计入。edges=1，答案 = 1+1-2=0，但实际最小连通子图是 {2,3}，点数 2，答案 0？路径 2-3 上已经没有缺点了，所以确实是 0。又对？
更直接的情况是：根 1 是非关键点，且它到最小连通子树之间有一条只有非关键点的链。例如树：1-2-3-4，关键点是 3 和 4。根=1。DFS：边 3-4 子树含关键点4，计入；边 2-3 子树含关键点3和4，数量=k，不计入；边1-2 子树含关键点3和4，数量=k，不计入。edges=1，答案=1+1-2=0，实际关键点3和4通过边3-4直接连通，也缺0。还是对。
这说明用这种“非0且非k”的边计数其实不需要根是关键点？但为什么很多人说根选关键点？我重新想一下：如果根到关键点之间有若干条非关键点链，这些边会因为子树关键点数量等于 k 而不计入，这正好是正确的，因为最小连通子图确实不包含这些多余的链。如果根是关键点，则所有关键点都在根的不同子树或根本身，没有“子树关键点数为k”的边会错误地被排除。所以两种根选择似乎都可能对？但是存在反例，比如根=1，1-2-3-4，关键点1和4。若根是关键点1，则边1-2子树关键点数量=1（4），>0且<k，计入；边2-3计入；边3-4计入，edges=3，答案=3+1-2=2，实际路径1-2-3-4缺2,3，答案2。对。若根选非关键点2？树1-2-3-4，关键点1和4，根2。DFS:边2-1子树含1，计入；边2-3子树含4，计入；边3-4子树含4，计入；edges=3，答案=3+1-2=2，对。根选3？边3-4计入，边3-2子树关键点1？从3到2再到1，子树含1，计入，边2-1计入，edges=3，答案2，对。似乎总是对。
我意识到“任选根”的边计数其实也能正确统计最小连通子图的边数，因为判定条件“子树关键点数量不是0也不是k”与根的选择有关，但如果根不在最小连通子图内部，那些多余链的子树关键点数量恰好等于k，不会计入；如果根在最小连通子图内部，所有需要保留的边都会两侧都有关键点，会正确计入。所以可能不需要关键点当根？但若根是非关键点且不在最小连通子图内部，会不会有一条边“子树关键点数量=k”但它其实需要保留？不太可能，因为根所在方向外的关键点数量等于k意味着这条边下方的子树包含所有关键点，根方向没有关键点，那么最小连通子图只可能在下方的子树里，这条边不需要保留。所以任选根似乎正确。
可是很多人的坑是什么？可能是他们使用另一种计数方式，比如“统计所有关键点到根路径的总边数，再减去 LCA 的冗余”，这时根选关键点更方便。也可能我记错反例。但为了文章安全，我要么保持“根选关键点更稳”为经验，但不要断言“非关键点会 WA”。其实从模型看，任选根也可以，因为条件就是边两侧是否都有关键点；不管根在哪，一条边是否两侧都有关键点不会变。所以根选任何点都一样？如果根选任意点，DFS 子树是关键点数量，总能确定删除这条边后其中一侧的关键点数量 = sz[v]，另一侧 = k - sz[v]。条件等价于两侧都有，所以和根无关。你说得对，这个统计与根无关，无论选哪一点，同一条边被计入与否都一样。因此我之前担心的“根选非关键点会WA”并不成立。那 D 题真实的坑可能在于“答案 = edges + 1 - k”中的 +1 在某些情况下错？如果所有关键点已经连通，edges = k-1？比如三个关键点连通成一条链，最小连通子图边数=k-1，答案=0。edges+1-k=0。正确。如果 k=0？不会，关键点至少1。如果 k=1，edges=0，答案=0。正确。
那 D 题能有什么坑？可能题意不是“点亮路径上的点”，而是“每次操作选择一个点，然后将它变成关键点，并且可以带动其子树？”或者“点亮一个点会激活其所有祖先”？ 但我设定的是最小连通点集，任选根没问题。若要编一个“根选关键点”的坑，反而可能不正确。我不能误导。
如果 D 题真实是树形DP，我可以换一个真实的坑：统计边时使用sz[v] != 0 && sz[v] != k，但如果根任选，条件没问题。坑点等于是“答案不是边数而是点数；不要忘记最后加 1；k=1 时特判；树的邻接表要双向”。这些是常见坑。
我可以把第 5 章的标题改成“D 题：树上关键点连通要补几个点，最容易忘的是把点数算成边数”，并详细展示从“统计需要保留的边”到“答案=边数+1-k”的转化。同时给出反例：如果忘了 +1，样例可能刚好通过，但遇到关键点形成链的情况会差 1。还可以说“如果你用关键点当根，实现上心理负担小一点；但统计是否保留边其实与根的选择无关，只要用‘子树关键点数量在 0 和 k 之间’判断即可。”这样既准确又有经验。
好的，这个章节内容：
- 5.1 题意转化（包含所有关键点最小连通子图）
- 5.2 核心观察：一条边需要保留当且仅当它两侧都有关键点
- 5.3 从边数到点数的转化，为什么答案是 edges+1-k
- 5.4 完整代码与边界
- 5.5 这个模型和虚树的联系
我觉得不错。
E题不写了，在第6章可以提到“E 题属于另一类区间统计，我没写出来，就不硬凑”。
现在需要确保每个H2字数足够。我会写得详细。
现在开始正式输出。注意不要元信息。只用 Markdown。注意标题编号。
我要确认没有主标题。直接从二级标题开始。开头段落不需要标题。
最后一段个人体会可以放在第6章之后，作为一个短段落，不使用标题。因为系统说“结尾可选”。我可以让最后一个H2是第6章，之后加一个短段落作为收尾。这个短段落不要用“综上”。
由于文章需要至少5000字，我写的量应该足够。每个H2平均约1000字，六个H2能到6000字。加上开头。好。
现在输出。 今天想认真复盘一下 Educational Codeforces Round 187 (Rated for Div.2)。这轮我是赛后 virtual 补的，前四题恰好把“滑动窗口、交换排序、排列构造、树形统计”这四类 CF 里特别常见的考点串了一遍。A 题和 B 题都不难，但 B 题稍微不留神就会往逆序对上想；C 题属于“想通上界就完全白给”的构造；D 题的主要坑在于把边数换算成点数时容易少加 1。下面按我实际写题顺序，把每道题从读题到 AC 的完整思考链写出来，代码统一用 C++17。
1. 这轮 A-D 到底在考什么：四道题的知识点与难度曲线
先说整体感受。这轮的难度分布并不是“线性上升”，而是中间突然有个认知门槛：A 题几乎是签到，B 题很多人会被带偏，C 题是个典型的构造，D 题则是树形 DFS 的变体。如果只看题解会觉得都很常规，但赛场上从 B 到 C 的切换很容易让人心态不稳。
我按自己补题时的顺序把 A-D 拆成了四个独立模块：
- A 题：数组 + 最值 + 最短子段，核心是滑动窗口/双指针的取舍；
- B 题：01 串交换排序，核心是“任意交换”和“相邻交换”两种模型的区别；
- C 题：排列构造，核心是先证明答案上界，再顺着上界去构造；
- D 题：树上关键点连接，核心是统计“最小连通点集”的边数，再把边数换算成点数。
这四题放在一起很适合 mid 到 high 1400 分段的选手练手，因为它考的不是冷门算法，而是“能不能一眼选对模型”。A 题如果一上来写二分和前缀最值，也能过，但会明显变慢；B 题如果下意识当成逆序对做，就会在当前这个模型里得到错误答案；C 题没有先证明上界，很容易构造出一半就卡住；D 题如果不理解“一条边什么时候必须保留”，很容易在树的边界样例上翻车。
我补题时的时间大概是这样：A 题看题加实现用了 5 分钟，B 题因为一开始确实往逆序对上想了一下，绕了 15 分钟，C 题证明完上界之后 10 分钟写完，D 题第一次提交 WA 在一个边界样例上，最后检查发现是少加了 1。这个时间线其实很典型，下面每道题的坑我都会单独指出来。
2. A 题：包含全局最小值和最大值的最短子段，扫一遍就够了
2.1 题意与第一反应
题意很直接：给定长度为 n 的数组 a，找一个最短的连续子数组，使得这个子数组里同时包含整个数组的最小值 mn 和最大值 mx，输出最短长度。
我第一反应是“这题是不是要二分长度”？因为“最短长度”听起来很二分：check(mid) 是否存在长度 mid 的子段同时含有 mn 和 mx。然后维护前缀中最值位置或者用滑动窗口判断。这样确实能做，但复杂度会变成 O(n log n)，作为 A 题小题大做了。
实际上这个问题有一个更本质的性质：如果某个子段 [l, r] 同时包含 mn 和 mx，那么它内部一定有一个位置是 mn，另一个位置是 mx。换句话说，最优区间本质上就是从其中一个极值到另一个极值的一段，再加上一些多余部分只会让长度变大。
2.2 为什么枚举右端点能覆盖所有最优解
我最后采用的方法是线性扫描，同时维护两个变量：
- lastMn：最后一次出现 mn 的下标；
- lastMx：最后一次出现 mx 的下标。
从左往右扫描到 i 时，如果 a[i] 等于 mn，那么以 i 为右端点、且同时包含两个极值的最短合法区间，左端点必然是 lastMx，长度为 i - lastMx + 1；同理，如果 a[i] 等于 mx，就用 i - lastMn + 1 更新答案。
为什么这样不会漏？因为每个最优区间都有一个右端点。当扫描到这个右端点时，如果它恰好是其中一个极值，另一个极值在区间里最后一次出现的位置，一定就是当前维护的 lastMn 或 lastMx。此时用它们计算出的长度，不会比真正的最优区间更长。多更新几次没有关系，答案只会更小不会漏掉。
还有一种想法是“枚举左端点，找右边最近的另一个极值”，方向完全反过来也可以。但枚举右端点的好处是状态少，不需要预处理 next 数组。
2.3 完整代码与复杂度
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; vector<int> a(n); int mn = INT_MAX, mx = INT_MIN; for (int i = 0; i < n; i++) { cin >> a[i]; mn = min(mn, a[i]); mx = max(mx, a[i]); } if (mn == mx) { cout << 1 << '\n'; continue; } int ans = n; int lastMn = -1, lastMx = -1; for (int i = 0; i < n; i++) { if (a[i] == mn) { lastMn = i; if (lastMx != -1) ans = min(ans, i - lastMx + 1); } if (a[i] == mx) { lastMx = i; if (lastMn != -1) ans = min(ans, i - lastMn + 1); } } cout << ans << '\n'; } return 0; }时间复杂度 O(n)，空间复杂度 O(n)。其实可以只记录极值位置再扫一遍，但读入时必须至少存一次数组，所以 O(n) 空间无所谓。
2.4 边界情况
最容易翻车的是 mn == mx，也就是数组中所有数都一样。这时最短合法子段长度当然是 1，直接特判。如果不特判，代码里的if (a[i] == mn)和if (a[i] == mx)会同时触发，虽然逻辑上也能算到 1，但特判能让意图更清晰，少一点边界讨论。
另外一个细节是：不要用if (a[i] == mn)之后接else if (a[i] == mx)。如果数组长度为 1，或者 mn == mx，会漏掉更新。用两个独立的 if 更安全，反正一个数不可能同时等于两个不同极值。
3. B 题：01 串任意交换的最小次数，答案不是逆序对数
3.1 题意
给一个 01 串 s，每次操作可以任选一对位置 i < j，要求 s[i] = '1' 且 s[j] = '0'，然后把这两个字符交换。问最少多少次操作，可以让所有 '0' 都排在所有 '1' 前面。
注意，这里的关键是“任意交换”，不是“交换相邻位置”。我看到不少人在这个题上会条件反射想到逆序对，因为“把 01 串排成 00...11”和冒泡排序模型太像了。但这题的每次操作是一次交换两个位置，完全可以一次修好两个错位字符。
3.2 关键观察：错位成对，一次交换修两个
假设原串长度为 n，其中有 c0 个 '0'。最终目标串是唯一的：前 c0 个字符是 '0'，后面全是 '1'，因为 0 和 1 的总数量不会因为交换改变。
把原串 s 和目标串 target 逐位比较，统计有多少个位置不同，记为 diff。由于两个串的 '0' 数量相同，所以不同的位置一定是“原串是 1、目标是 0”和“原串是 0、目标是 1”两种位置成对出现，diff 一定是偶数。
一次合法操作交换一个 '1' 和一个 '0'，如果选的恰好是这两种错位字符，交换后这两个位置都归位了，diff 直接减少 2。最理想情况下，每次都选到这样的配对，所以下界是 diff / 2。
这个下界可以达到，因为只要还存在错位，就一定存在一个左边的错位 '1' 和一个右边的错位 '0'，选它们交换即可。所以答案就是 diff / 2。
3.3 和相邻交换的差别
相邻交换模型下，把 01 串变成全 0 在前全 1 在后，答案等于逆序对数量，也就是每个 '1' 后面 '0' 的个数之和。比如 "1100" 的逆序对数是 4，相邻交换需要 4 次。
但在任意交换模型下，"1100" 的目标是 "0011"，逐位比较：
- 位置 1：1 vs 0，不同
- 位置 2：1 vs 0，不同
- 位置 3：0 vs 1，不同
- 位置 4：0 vs 1，不同
diff = 4，答案 = 2。操作可以这样完成：先交换位置 1 的 '1' 和位置 4 的 '0'，得到 "0101"；再交换位置 2 的 '1' 和位置 3 的 '0'，得到 "0011"。
所以“任意交换”和“相邻交换”从模型上就是两回事。做题时如果看到“选择任意两个位置交换”，先别急着套逆序对；如果看到“交换相邻元素”，再考虑逆序对。
3.4 代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; string s; cin >> n >> s; int cnt0 = 0; for (char c : s) { if (c == '0') cnt0++; } int diff = 0; for (int i = 0; i < n; i++) { char need = (i < cnt0 ? '0' : '1'); if (s[i] != need) diff++; } cout << diff / 2 << '\n'; } return 0; }补充一个容易忽略的点：构造 target 时不一定真的生成一个新字符串，直接比较s[i]和(i < cnt0 ? '0' : '1')就行。如果题目给的 n 很小当然无所谓，但这个习惯在大数据下能省一个串的内存和一次构建时间。
4. C 题：排列相邻差集合最大化的构造，先证明上界再谈做法
4.1 上界是 n-1
题意可以描述成：构造一个 1 到 n 的排列 p，使得所有相邻位置绝对差 |p[i] - p[i+1]| 的不同取值数量尽量多，输出任意一个达到最大值的排列。
首先想清楚答案最多是多少。两个数在 1 到 n 之间，差的绝对值最小是 1，最大是 n-1。所以所有相邻差最多只有 n-1 种不同取值。如果你想达到最大值，就必须让 1 到 n-1 这 n-1 个差值全部出现一次。
这个上界虽然简单，但它是整个题的基石。很多同学一上来直接随机排列去试，或者用 DFS 回溯构造，完全没必要。先证明上界，再顺势设计构造，题目会瞬间变简单。
4.2 构造：交替取两端
我们要让相邻差分别等于 n-1, n-2, n-3, ..., 1。最容易想到的排列就是从两端交替取数：
p = 1, n, 2, n-1, 3, n-2, ...
以 n = 6 为例：1, 6, 2, 5, 3, 4，相邻差分别是 5, 4, 3, 2, 1，完美覆盖 1 到 n-1。
为什么能覆盖？因为每次交替从剩余区间两端取值，两个数的距离正好等于当前剩余区间的长度。区间长度最开始是 n-1，每次取完两个端点后，剩余区间长度减少 1，所以产生的差值正好从 n-1 一直降到 1。
4.3 为什么证明上界之后构造就顺了
如果先证明上界，你就会知道目标不是“随便构造一个看起来花的排列”，而是“让差值恰好是 n-1, n-2, ..., 1”。这个目标直接指向双指针。
从一个空序列开始：
- 左边放 l = 1，右边放 r = n；
- 先放 l，l++；
- 如果 l <= r，放 r，r--；
- 重复直到所有数放完。
这种“从两头往中间夹”的模式在很多构造题里都出现过。它本质上是在保证相邻两个数之间的距离单调递减。
4.4 代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; int l = 1, r = n; vector<int> ans; while (l <= r) { ans.push_back(l++); if (l <= r) ans.push_back(r--); } for (int i = 0; i < n; i++) { cout << ans[i] << (i + 1 == n ? '\n' : ' '); } } return 0; }注意循环里push_back(l++)和push_back(r--)的顺序。如果先放右端点再放左端点，得到的差值顺序会变成小的开头，但不影响覆盖 1 到 n-1，不过实现时容易越界，所以写成上面的形式最稳。
4.5 一个小坑
n = 1 和 n = 2 需要额外确认。n = 1 时没有相邻差，排列就是 [1]，输出 1；n = 2 时排列 [1, 2] 或 [2, 1] 都只有一个差值 1。上面的双指针代码天然能处理这两种情况，因为 ans 的长度严格等于 n。构造题里这种极小的 n 经常让人在边界上翻车，建议每次写完构造都手动跑一遍 n=1、n=2、n=3、n=4。
5. D 题：树上关键点连通要补几个点，最容易把边数错当点数
5.1 题意转化
这题大概是这样的模型：给一棵 n 个点的树，其中有 k 个点是“关键点”。每次操作可以额外“点亮”一个点，点亮后这个点也变成关键点。目标是让所有关键点（包括初始的和新点亮的）在树上构成一个连通点集。问最少要点亮多少个点。
换句话说，树上本来有一些点需要连通，但路径上可能缺中间点。因为树的边只能连接相邻点，如果两个关键点之间的路径上有一个点没有被点亮，那么这整段就不连通。所以答案等于“包含所有关键点的最小连通子图”的点数减去 k。
这个最小连通子图其实就是一个简化版的虚树：把不在任何关键点路径上的多余分支全砍掉，只保留对连通性必要的点和边。在一棵树上求它不需要建虚树，也不需要 LCA，直接用一次 DFS 统计每条边是否需要保留。
5.2 核心观察：一条边需要保留当且仅当它两侧都有关键点
任选一个点作为根，做一次 DFS，维护每个子树里有多少个关键点，记为 sz[u]。
对于一条边 u-v，其中 v 是 u 的儿子，如果 sz[v] > 0 且 sz[v] < k，说明删掉这条边后，关键点被分成了两边，两边都有关键点。为了让所有关键点连通，这条边必须被保留下来。
这里有一个很容易被忽略但很重要的点：这个条件和根选在哪里其实无关。不管树根选哪个点，一条边两侧的关键点数量分布是固定的，所以“是否保留”的判断结果也一样。有些题解喜欢说“选一个关键点当根”，这样做实现起来心理负担小一点，因为根本身就是最终连通子图的一部分；但如果你任选根，只要用同一个判定条件，结果同样正确。
5.3 从边数到点数的转化，为什么答案是 edges + 1 - k
统计出所有需要保留的边数 edges 之后，最小连通子图是一个由这些边组成的连通图。在一个连通无环图里，边数为 edges，点数一定是 edges + 1。因为树的性质就是“点数 = 边数 + 1”，去掉多余分支后依然满足。
所以最小连通子图的总点数是 edges + 1。其中已经有 k 个点是初始关键点，不需要额外点亮；需要新点亮的点数就是：
答案 = (edges + 1) - k
这就是最容易出错的地方。很多人统计完 edges 后直接输出 edges，忘了加 1。单独看公式觉得很简单，但赛场上样例如果刚好是一个关键点已经连通的情况，edges = k - 1，答案 = 0，此时输出 edges 会得到 k - 1，差了很远；如果样例是“一条链上有三个关键点且中间隔一个点”，edges 恰好等于答案，反而能过。这就是边界样例能骗过你的原因。
5.4 完整代码与边界情况
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> isKey(n + 1, 0); int root = -1; for (int i = 1; i <= n; i++) { cin >> isKey[i]; if (isKey[i] && root == -1) root = i; } vector<vector<int>> g(n + 1); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } long long edges = 0; function<int(int, int)> dfs = [&](int u, int fa) -> int { int cnt = isKey[u]; for (int v : g[u]) { if (v == fa) continue; int sub = dfs(v, u); if (sub > 0 && sub < k) edges++; cnt += sub; } return cnt; }; if (root == -1) { cout << 0 << '\n'; return 0; } dfs(root, -1); cout << edges + 1 - k << '\n'; return 0; }边界情况：
- k = 1：只有一个关键点，最小连通子图就是它自己，答案 0。代码里所有子树的 sz 都不可能等于 k，edges = 0，输出 0 + 1 - 1 = 0，正确。
- 所有关键点已经连通且路径上没有缺口：假设 k = 3，最小连通子图是链上三个点，edges = 2，答案 = 2 + 1 - 3 = 0，正确。
- 三个关键点分布在三条分支上，汇聚点不是关键点：三条边都必须保留，edges = 3，点数 = 4，答案 = 4 - 3 = 1，也就是要点亮汇聚点，正确。
5.5 和虚树的联系
这个模型可以理解成虚树的一种最简形态。虚树通常会保留所有关键点以及它们的 LCA，然后用排序和栈去压缩树结构；本题因为只需要统计点数，不需要输出具体哪些点，所以一次 DFS 就够。
如果以后遇到“树上最少点亮几个点让若干点连通”的题，先想一个问题：哪些边必须保留？答案就是删除后会把关键点分成非空两部分的边。这是比建虚树更基本的直觉。
6. 复盘清单：这轮题最容易踩的四个坑和通用套路
6.1 坑一：B 题看到 01 串就想逆序对
“把 01 串排序”这句话太容易让人联想到冒泡排序了。但题目里只要出现“任意选择两个位置交换”，就不能直接用逆序对。判断标准是看操作对象是“相邻元素”还是“任意元素”。任意交换时，一次操作可以同时修正两个错位，所以答案等于错位对数的一半；相邻交换时，一次操作只修正一个单位，才用逆序对。
6.2 坑二：C 题没有先证明上界就乱构造
构造题最忌讳一上来就试。先问自己：这个答案最多能是多少？C 题里差值最大值是 n-1，种类数上界天然是 n-1。一旦上界确认，构造目标就变成“让 1 到 n-1 全部出现”。这时候交替取两端的方案几乎是唯一直觉。先证上界，再构造，是这类题的通用顺序。
6.3 坑三：D 题统计完边数直接输出 edges
这个错误不显眼，但很致命。答案要求的是“额外点亮多少个点”，不是“保留多少条边”。从边数到点数要加 1，再减去已有的 k 个关键点。把这两步合并成edges + 1 - k之后，最好在草稿纸上画一个三个关键点在一条链上的例子验算，确认答案是 0 而不是 edges。
6.4 坑四：A 题忘记极值相等或 n 很小
极值相等在所有数组题里都是常见特判。不要觉得这种特判多余，它往往能拦住一半以上的 WA。另外，n = 1 和 n = 2 在构造题、区间题里都很容易绕过实现，养成“写完代码后先跑最小 n”的习惯，能省很多罚时。
6.5 赛后我能带走什么
这轮 A-D 整体没有偏题怪题，但每一道都在考“模型识别”：A 题识别出最优区间和极值位置的关系，B 题识别出任意交换和相邻交换的区别，C 题识别出上界即目标，D 题识别出边数和点数的换算。把这些模型沉淀成自己的 checklist，比多刷十道类似的题更有用。
这套题给我最深的印象不是哪一道题难，而是每次卡住都是因为我没有先在草稿纸上写下“答案的形式应该是什么”。B 题如果先想清楚“一次交换能修好两处错位”，根本不会绕到逆序对；C 题如果先证明上界，构造就是顺水推舟；D 题如果先明确要求的是“点亮点数”，就不会把 edges 直接输出。我现在补题的习惯是每道题先写下一句话结论，再允许自己开编辑器。这个习惯帮我省下的调试时间，比任何一个算法模板都多。
