题目回顾

我们有 $n$ 棵树，高度为 $h_1, h_2, \dots, h_n$，定义不整齐程度为：

$$\sum_{i=1}^{n-1} |h_i - h_{i+1}|$$

我们可以选择交换任意两棵树（也可以不交换），对于每一棵树 $i$，求交换它和另一棵树后（或自身不交换）整个序列不整齐程度的最小值。

---

思路总览

1. 基础分析

设原序列的不整齐程度为 $S$。

如果我们交换位置 $i$ 和 $j$（$i < j$），那么只有 $i-1 \to i$，$i \to i+1$，$j-1 \to j$，$j \to j+1$ 这几条边的值会改变（注意边界情况）。

因此，我们可以先预处理出每个位置在原始序列中的“代价”：

• 对于 $1 < i < n$，$c[i] = |h_i - h_{i-1}| + |h_i - h_{i+1}|$
• 对于 $i=1$，$c[1] = |h_1 - h_2|$
• 对于 $i=n$，$c[n] = |h_n - h_{n-1}|$

交换 $i$ 和 $j$ 后，新的不整齐程度为：

$$S - c[i] - c[j] + \text{new\_edges}(i,j)$$

其中 $\text{new\_edges}(i,j)$ 是交换后 $i$ 和 $j$ 周围新边的绝对值之和。

---

2. 交换的三种情况

(a) 交换相邻位置 $i$ 和 $i+1$

此时只有 $i-1 \to i$，$i \to i+1$，$i+1 \to i+2$ 这三条边会变化（注意边界）。这种情况可以 $O(1)$ 计算。

(b) 交换 $i$ 和 $j$ 不相邻（$j > i+1$）

这时 $i$ 和 $j$ 的邻域不相交，所以：

• 对于 $i$，新边是 $|h_j - h_{i-1}| + |h_j - h_{i+1}|$
• 对于 $j$，新边是 $|h_i - h_{j-1}| + |h_i - h_{j+1}|$

于是：

$$\text{new\_total} = S - c[i] - c[j] + |h_j - h_{i-1}| + |h_j - h_{i+1}| + |h_i - h_{j-1}| + |h_i - h_{j+1}| $$

---

3. 核心优化

直接枚举 $i,j$ 是 $O(n^2)$，不可行。

观察公式：

对于固定的 $i$（$1 < i < n$），设：

$$A_1 = h_{i-1},\quad A_2 = h_{i+1}$$

并假设 $A_1 \le A_2$（否则交换它们）。

那么 $i$ 的新边贡献是：

$$|h_j - A_1| + |h_j - A_2|$$

这个函数关于 $h_j$ 是分段线性的：

• 若 $h_j \le A_1$，则 $= -2h_j + (A_1 + A_2)$
• 若 $A_1 \le h_j \le A_2$，则 $= (A_2 - A_1)$
• 若 $h_j \ge A_2$，则 $= 2h_j - (A_1 + A_2)$

---

4. 数据结构使用

我们需要对每个 $i$，找到某个 $j$（$j \neq i, i\pm 1$）使得：

$$\text{score} = -c[i] - c[j] + |h_j - A_1| + |h_j - A_2| + |h_i - B_1| + |h_i - B_2| $$

最小，其中 $B_1 = h_{j-1}$，$B_2 = h_{j+1}$。

这可以看作：固定 $i$，枚举 $j$，但 $j$ 的 $B_1, B_2$ 是固定的，所以我们可以把 $j$ 的信息按 $h_j$ 的值分类存储到线段树中，每个节点存储三种线性函数的最小值（对应 $h_j$ 在三个区间的情况）。

---

5. 代码结构

1. 预处理：

   • 计算原始总代价 $S$
   • 计算每个位置的 $c[i]$
   • 离散化高度

2. 相邻交换：

   • 直接枚举相邻对 $(i, i+1)$ 计算

3. 与端点交换：

   • 交换 $1$ 与 $j$
   • 交换 $n$ 与 $j$
   • 直接枚举 $j$ 计算

4. 不相邻交换：

   • 使用三个线段树（seg0, seg1, seg2）分别维护 $h_j$ 在三个区间的信息
   • 按 $h_j$ 排序查询和更新
   • 对每个 $i$，根据 $h_j$ 与 $[A_1, A_2]$ 的关系在线段树中查询最小值

---

6. 线段树设计

每个线段树节点存储一个大小为 3 的数组，表示：

• tr[0]：对应 $h_j \le A_1$ 情况下的最小值（形式 $K - 2h_j$）
• tr[1]：对应 $A_1 \le h_j \le A_2$ 情况下的最小值（常数）
• tr[2]：对应 $h_j \ge A_2$ 情况下的最小值（形式 $K + 2h_j$）

插入/删除时更新，查询时根据 $h_j$ 的范围取对应值。

---

7. 算法复杂度

• 相邻交换和端点交换：$O(n)$
• 不相邻交换：$O(n \log n)$（排序 + 线段树操作）
• 总复杂度：$O(n \log n)$

---

总结

这道题的关键在于：

1. 发现交换只影响局部边
2. 将绝对值函数分段线性化
3. 使用数据结构维护最优值，避免 $O(n^2)$ 枚举
4. 注意边界情况的单独处理

核心是分情况处理 + 线段树优化查询，属于经典的数据结构优化问题。