题意理解

有 ( N ) 堆草排成一行，高度为 ( h_1, h_2, \dots, h_N )。Bessie 可以交换相邻的两堆草，当且仅当它们的高度差不超过 ( K )。可以进行任意多次这样的操作，目标是得到字典序最小的最终高度序列。

核心思路

关键观察

1. 交换的传递性
   如果 A 能和 B 交换，B 能和 C 交换，那么 A 也能和 C 交换（通过 B 作为中介）。

2. 连通块概念
   所有能通过一系列交换互相到达的草堆构成一个"连通块"。在同一个连通块内的草堆可以任意重新排列。

3. 字典序贪心
   要得到字典序最小的序列，应该从左到右依次决定每个位置放哪个草堆，每次都选择当前能放到该位置的最小值。

算法步骤

1. 确定每个位置能放哪些草堆

对于位置 ( i )，能放在这里的草堆必须满足：

• 它目前还在剩余草堆中
• 它能够通过一系列交换到达位置 ( i )

2. 贪心构造

维护一个数据结构（如平衡树或堆）来存储当前可用的草堆：

1. 初始化：将所有草堆加入数据结构
2. 对于每个位置 ( i = 1 ) 到 ( N )：
   • 从数据结构中找出最小的能放到当前位置的草堆
   • 将该草堆放到位置 ( i )
   • 从数据结构中移除这个草堆
   • 更新可用草堆集合（新的草堆可能因为前面的移除而变得可用）

3. 判断可达性

关键问题：如何快速判断一个草堆是否能放到当前位置？

解法：维护当前"连通块"的边界。一个草堆能放到位置 ( i ) 当且仅当：

• 它与位置 ( i ) 在同一个连通块中，或者
• 它所在的连通块与位置 ( i ) 的连通块通过一系列高度差 ≤ K 的相邻草堆相连

复杂度分析

• 时间复杂度：( O(N \log N) ) 或 ( O(N \log^2 N) )，取决于具体实现
• 空间复杂度：( O(N) )

实现细节

可以用以下数据结构：

• 平衡树（如 std::set）维护当前可用的最小草堆
• 并查集或单调栈来维护连通块关系
• 线段树来快速查询区间最小值和判断可达性

总结

本题的关键在于认识到：

1. 高度差限制实际上定义了草堆之间的连通关系
2. 在连通块内部可以任意重排
3. 字典序最小可以通过从左到右的贪心选择来实现

这是一个典型的贪心 + 数据结构问题，需要高效地维护可用选择和更新连通关系。