27093: 排队又来了

Segment Tree, Discretization（离散化）, binary search, http://cs101.openjudge.cn/practice/27093/

题面含义与 25353: 排队一致，但是提供了更大的测试数据，O(n^2)会超时。

25353:排队

http://cs101.openjudge.cn/practice/25353/

2023年选北京大学计算概论B课程学生郭绍阳同学题解。

https://www.cnblogs.com/guoshaoyang/p/17824372.html

线段树+离散化

理解这道题的核心在于从“局部交换”推导出“全局约束”。

一、核心逻辑解读：从“交换”到“障碍”

1. 交换的本质 题目规定：相邻且身高差 $\leq D$ 可以交换。反过来想：如果两个人的身高差 $> D$ ，他们就永远无法跨越彼此。

2. 偏序关系的建立 对于任意两个位置 $i < j$ （ $i$ 在 $j$ 左边）：

如果 $| h_{i} - h_{j} | > D$ ，那么在最终结果中， $h_{i}$ 必须依然在 $h_{j}$ 的左边。
如果 $| h_{i} - h_{j} | \leq D$ ，他们的相对顺序是可调的（前提是中间没有其他障碍）。

这构成了一个 有向无环图 (DAG)，每一对满足 $| h_{i} - h_{j} | > D$ 且 $i < j$ 的元素之间都有一条 $i \to j$ 的边。我们要找的是这个 DAG 的字典序最小的拓扑排序。

二、算法优化：为什么用“分层”？

通常求字典序最小的拓扑序使用 Kahn 算法 + 优先队列。但本题 $N = 10^{5}$ ，边数可能达到 $O (N^{2})$ ，无法显式建图。

核心结论： 本题具有特殊性，其约束只取决于“比我小很多”或“比我大很多”的元素。我们可以定义一个“层级 (Layer)”：

$L a y e r (h_{i}) = 1 + max {L a y e r (h_{j}) ∣ j < i, | h_{i} - h_{j} | > D}$
如果前面没有不可交换的元素，则该元素处于第 1 层。

为什么分层排序是正确的？

同层元素： 彼此之间不存在强约束（或者通过中间节点可以灵活调动），可以为了追求字典序最小而任意排序。
异层元素： 如果 $L a y e r (A) < L a y e r (B)$ ，说明 $B$ 的前面一定存在一个（或一串）它跨不过去的元素，且那个元素直接或间接约束了 $B$ 必须在 $A$ 相关集合的后面。

因此：最终序列 = 第1层排序输出 + 第2层排序输出 + ...

三、工业级实现：线段树 + 离散化

由于身高 $h_{i}$ 高达 $10^{9}$ ，我们需要：

离散化：将身高映射到 $[0, M - 1]$ 。
动态维护最大值：当我们处理到第 $i$ 个元素时，需要快速查询：
- 身高在 $[1, h_{i} - D - 1]$ 范围内的最大层级。
- 身高在 $[h_{i} + D + 1, max_H]$ 范围内的最大层级。
线段树 (Segment Tree)：支持单点更新和区间查询最大值。

四、代码实现（使用快读和迭代版线段树）

python

import sys
import bisect

def solve():
    # 使用快读提高效率
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    D = int(input_data[1])
    info = list(map(int, input_data[2:]))

    # 1. 离散化
    # heights 存储所有去重后的身高，用于定位区间
    heights = sorted(set(info))
    h_to_idx = {h: i for i, h in enumerate(heights)}
    m = len(heights)

    # 2. 迭代式线段树 (比递归式快得多)
    size = 1
    while size < m:
        size *= 2
    tree = [0] * (2 * size)

    def update(i, val):
        i += size
        tree[i] = val
        while i > 1:
            i //= 2
            tree[i] = max(tree[2 * i], tree[2 * i + 1])

    def query(l, r):
        res = 0
        if l > r:
            return res
        l += size
        r += size
        while l <= r:
            if l % 2 == 1:
                if tree[l] > res: res = tree[l]
                l += 1
            if r % 2 == 0:
                if tree[r] > res: res = tree[r]
                r -= 1
            l //= 2
            r //= 2
        return res

    # 3. 计算每一层的元素
    # layers[k] 存储所有属于第 k 层的身高
    layers = []
    # 预先分配空间或使用 dict，Python 中 list 扩容较快
    # 我们用一个字典来存，最后排序 key 即可
    from collections import defaultdict
    layer_map = defaultdict(list)

    for h in info:
        idx = h_to_idx[h]
        
        # 找到不能交换的范围： < h-D 或 > h+D
        # 即可交换范围是 [h-D, h+D]
        # 我们查询这个范围之外的最大层级
        
        # L_idx 是第一个 >= h-D 的位置，那么左侧不可交换区间为 [0, L_idx-1]
        L_idx = bisect.bisect_left(heights, h - D)
        # R_idx 是第一个 > h+D 的位置，那么右侧不可交换区间为 [R_idx, m-1]
        R_idx = bisect.bisect_right(heights, h + D)
        
        max_prev_layer = max(query(0, L_idx - 1), query(R_idx, m - 1))
        
        current_layer = max_prev_layer + 1
        layer_map[current_layer].append(h)
        
        # 更新线段树：在当前身高的位置记录其层级
        update(idx, current_layer)

    # 4. 按层级顺序，层内排序输出
    ans = []
    for k in sorted(layer_map.keys()):
        # 同一层内的元素可以自由交换顺序以达到字典序最小
        layer_map[k].sort()
        ans.extend(layer_map[k])

    print(*(ans))

if __name__ == "__main__":
    solve()

五、关键点深度总结

复杂度分析：
- 离散化： $O (N \log N)$
- 线段树操作： $N$ 次循环，每次 bisect + query + update 均为 $O (\log N)$ 。
- 排序输出： $O (N \log N)$ 。
- 总复杂度： $O (N \log N)$ ，对于 $N = 10^{5}$ 可以在 1 秒内完成。
字典序最小的保证：在这个 DAG 模型中，处于同一“层”的元素意味着它们在拓扑结构中是并列的，且它们之间没有“跨不过去”的障碍。因此，将每一层内部按升序排列，可以直接得到全局字典序最小的序列。

树状数组

1. 核心约束与本质： 题目规定：只有当相邻两名同学的身高差 $| h_{i} - h_{j} | \leq D$ 时，才能交换位置。反过来思考：如果两名同学的身高差 $| h_{i} - h_{j} | > D$ ，那么他们的相对顺序是永远无法改变的。这实际上定义了一个偏序关系（Partial Order）：对于原序列中任何一对 $i < j$ 且 $| h_{i} - h_{j} | > D$ 的数，在最终序列中 $h_{i}$ 必须出现在 $h_{j}$ 的左边。

2. 贪心策略与分层： 我们要寻找字典序最小的排列。在满足上述偏序关系的前提下，我们可以将元素进行“分层”。

层数 $L [i]$ 的含义：以 $h_{i}$ 结尾的、满足相邻元素不可交换的最长链的长度。
公式： $L [i] = 1 + max {L [j] ∣ j < i, | h_{j} - h_{i} | > D}$ 。
结论：所有层数相同的元素，彼此之间没有绝对的前后约束（或者其约束已被更低层数覆盖），因此为了让字典序最小，我们可以将所有元素先按层数 $L$ 升序排列，层数相同时按身高 $h$ 升序排列。

3. 算法优化： 由于 $N = 10^{5}$ ， $h_{i}$ 高达 $10^{9}$ ，直接遍历 $j < i$ 会导致 $O (N^{2})$ 。我们需要快速查询：

$h_{j} < h_{i} - D$ 范围内的最大层数。
$h_{j} > h_{i} + D$ 范围内的最大层数。这是一个动态维护的区间最值查询（RMQ）问题。我们可以通过离散化身高，配合树状数组（BIT）或线段树在 $O (N \log N)$ 时间内解决。

代码

python

import sys
from bisect import bisect_left, bisect_right

# 使用树状数组（Binary Indexed Tree）维护区间最大值
class BITMax:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)

    # 更新索引 i 处的最大值
    def update(self, i, val):
        while i <= self.n:
            if val > self.t[i]:
                self.t[i] = val
            i += i & -i

    # 查询前缀 [1, i] 中的最大值
    def query(self, i):
        res = 0
        while i > 0:
            if self.t[i] > res:
                res = self.t[i]
            i -= i & -i
        return res

def solve():
    # 快速读入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    d = int(input_data[1])
    h = list(map(int, input_data[2:]))

    # 1. 离散化：处理身高跨度过大的问题
    # vals 存储去重排序后的身高，用于建立坐标系
    vals = sorted(list(set(h)))
    m = len(vals)

    # 2. 初始化两个树状数组
    # bit_low: 维护身高较小部分的最大层数
    # bit_high: 维护身高较大部分的最大层数（通过镜像映射实现后缀查询）
    bit_low = BITMax(m)
    bit_high = BITMax(m)

    level = [0] * n

    for i, x in enumerate(h):
        # 寻找前面所有满足 |h_j - x| > D 的 j
        # 即：h_j < x - D 或 h_j > x + D
        
        # 找到小于 x - D 的最大身高在 vals 中的索引
        idx_low = bisect_left(vals, x - d) # 返回第一个 >= x-d 的位置，其左侧都 < x-d
        max_l_low = bit_low.query(idx_low)
        
        # 找到大于 x + D 的最小身高在 vals 中的索引
        idx_high = bisect_right(vals, x + d) # 返回第一个 > x+d 的位置
        # 对于后缀查询，我们映射索引：m - idx_high 转换成前缀形式
        max_l_high = bit_high.query(m - idx_high)

        # 当前元素的层数为前面约束它的最大层数 + 1
        level[i] = max(max_l_low, max_l_high) + 1

        # 更新树状数组
        # p 是当前身高 x 在离散化数组中的 1-based 索引
        p = bisect_left(vals, x) + 1
        bit_low.update(p, level[i])
        bit_high.update(m - p + 1, level[i])

    # 3. 核心排序逻辑
    # 字典序最小的解：优先按层数排序，层数相同按身高排序
    # zip(level, h) 将层数与身高配对，sorted 默认先比第一个元素再比第二个
    ans_pairs = sorted(zip(level, h))
    
    # 提取结果并输出
    print(*(p[1] for p in ans_pairs))

if __name__ == '__main__':
    solve()

关键点解读

离散化 (vals)：由于身高 $h_{i}$ 可能非常大（ $10^{9}$ ），无法直接作为树状数组的下标。离散化将原本稀疏的身高映射到 $[1, M]$ 的紧凑整数空间（ $M \leq N$ ），保证了树状数组的效率。
双向树状数组：
- bit_low.query(idx_low)：查询区间 $[0, x - D)$ 的最大层数。
- bit_high.query(m - idx_high)：查询区间 $(x + D, \infty)$ 的最大层数。这里 bit_high 使用了技巧：将位置 $p$ 映射为 $M - p + 1$ ，这样原本的后缀查询（从 $i d x$ 到 $M$ ）就变成了前缀查询。
排序依据：为什么 sorted(zip(level, h)) 是对的？
- 如果两个数 $A$ 和 $B$ 存在不可交换的偏序关系（比如 $A$ 在 $B$ 前面且 $| A - B | > D$ ），那么 $B$ 的层数必然大于 $A$ 。在排序时， $A$ 一定排在 $B$ 前面，满足了偏序约束。
- 如果两个数没有直接或间接的偏序约束，它们的层数可能相同。此时为了让字典序最小，我们自然选择身高较小的排在前面。
复杂度分析：
- 时间复杂度：离散化 $O (N \log N)$ ，树状数组查询与更新 $O (N \log N)$ ，排序 $O (N \log N)$ 。总复杂度 $O (N \log N)$ 。
- 空间复杂度： $O (N)$ ，用于存储身高、层数和树状数组。

样例执行流程 (7 7 3 6 2, D=3)

7: 前面无元素, L=1, bit_low更新位置(7), bit_high更新位置(7).
7: 前面无 $| h_{j} - 7 | > 3$ , L=1, 同上更新.
3: 前面 7-3=4 > 3, L = L(7)+1 = 2.
6: 前面无 $| h_{j} - 6 | > 3$ (7-6=1, 3-6=3), L=1.
2: 前面 7-2=5 > 3 (层数1), 6-2=4 > 3 (层数1), L = 1+1 = 2.

结果分层：
- 层1: [7, 7, 6] -> 排序后 [6, 7, 7]
- 层2: [3, 2] -> 排序后 [2, 3]
合并：6 7 7 2 3。符合样例输出。

感觉 27093:排队又来了，线段树（Segment Tree）在处理“区间查询”时确实比树状数组更符合人类的直觉。直观的区间映射：线段树可以直接查询 [0, L_idx - 1] 和 [R_idx, m - 1]。不需要像树状数组那样为了做后缀查询而去搞“镜像翻转”，也不用纠结 m - p + 1 这种复杂的下标变换。
树状数组BITMax写法，需要理解： 1）bisect_left 返回值的物理含义与树状数组 1-based 索引之间的一种完美契合。 2）以及 m - idx_high 的本质：将“大于某值的后缀区间”长度，转换成“镜像后的前缀区间”长度，从而复用树状数组的代码。

内存 31800KB，时间1086ms

python

# OJ25353 排队，23-数院-胡睿诚
# 树状数组数组下标从1开始，便于理解low_bit
from collections import defaultdict
import bisect

N,D = map(int,input().split())
#N, D = 5, 3
*info, = map(int, input().split())
#info = [7, 7, 3, 6, 2]

# 内存开不了1e9那么大，使用“离散化”技巧。
# 离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
# 通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

# 注意这里用set是因为我们每次只存储当前高度所对应（可能多个）点的层数最大值
heights = sorted(list(set(info)))

ass = {}
for i, h in enumerate(heights, 1):
    ass[h] = i  # 只是为了方便找到高度h排第几个

l = len(heights)
tree_l = [-1] * (l+1)   # 树状数组下标是1开始有效
tree_r = [-1] * (l+1)
#两个树状数组，分别记录从小到大和从大到小第i高的高度点所对应的层数
#这里用了变形的树状数组，不是来处理区间和而是来处理区间最大值
#这种树状数组的有效性依赖于每次修改都会把数改大，否则修改操作需要(logn)^2复杂度
ans = defaultdict(list)  # 存储分层结果：每层有哪些高度

# 树状数组辅助函数
def low_bit(x):
    return x & (-x)

def update(i, v, tree):
    while i <= l:
        tree[i] = max(v, tree[i])
        i += low_bit(i)

def get_max(i, tree):
    res = -1
    while i > 0:
        res = max(res, tree[i])
        i -= low_bit(i)
    return res


for h in info:  # 按照输入的顺序（即队伍顺序）扫描
    index = ass[h]
    left = bisect.bisect_right(heights, h-D-1) #left下标是0开始计算
    right = l - bisect.bisect_left(heights, h+D+1)
    storey = 1 + max(get_max(left, tree_l), get_max(right, tree_r))
    #递推关系。分别找到小于h-D与大于h+D的高度所对应层数的最大值
    update(index, storey, tree_l)
    update(l+1-index, storey, tree_r)
    #更新高度h对应的点的层数最大值
    ans[storey].append(h)  # 加入结果中

res = []
for storey in sorted(ans.keys()):
    res.extend(sorted(ans[storey]))
print(' '.join(map(str, res)))

这份代码使用了树状数组（Fenwick Tree）来维护每个身高的“层数”，并通过离散化技巧来处理大范围的身高值。下面是代码的时间复杂度分析和详细解释。

时间复杂度分析

离散化：
- 对身高进行排序：O(N log N)
- 构建离散化映射：O(N)
树状数组操作：
- 每次更新操作：O(log N)
- 每次查询操作：O(log N)
主循环：
- 遍历每个身高：O(N)
- 对每个身高进行两次查询和两次更新：O(log N)

综上所述，总的时间复杂度为：O(N log N)

代码详细解释

读取输入：

python

N, D = map(int, input().split())
*info, = map(int, input().split())

离散化：

将身高去重并排序，构建离散化映射。

python

heights = sorted(list(set(info)))
ass = {}
for i, h in enumerate(heights, 1):
    ass[h] = i

初始化树状数组：
- tree_l 和 tree_r 分别记录从小到大和从大到小第 i 高的高度点所对应的层数。
python
```
l = len(heights)
tree_l = [-1] * (l + 1)
tree_r = [-1] * (l + 1)
ans = defaultdict(list)
```

树状数组辅助函数：

low_bit：计算最低有效位。
update：更新树状数组中的值。
get_max：查询树状数组中的最大值。

python

def low_bit(x):
    return x & (-x)

def update(i, v, tree):
    while i <= l:
        tree[i] = max(v, tree[i])
        i += low_bit(i)

def get_max(i, tree):
    res = -1
    while i > 0:
        res = max(res, tree[i])
        i -= low_bit(i)
    return res

主循环：

遍历每个身高，计算其层数并更新树状数组。

python

for h in info:
    index = ass[h]
    left = bisect.bisect_right(heights, h - D - 1)
    right = l - bisect.bisect_left(heights, h + D + 1)
    storey = 1 + max(get_max(left, tree_l), get_max(right, tree_r))
    update(index, storey, tree_l)
    update(l + 1 - index, storey, tree_r)
    ans[storey].append(h)

输出结果：

按层排序并输出结果。

python

res = []
for storey in sorted(ans.keys()):
    res.extend(sorted(ans[storey]))
print(' '.join(map(str, res)))

27093: 排队又来了 ​

线段树+离散化 ​

树状数组 ​

27093: 排队又来了

线段树+离散化

树状数组