25353: 排队

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

有 N 名同学从左到右排成一排，第 i 名同学的身高为 hi。现在张老师想改变排队的顺序，他能进行任意多次（包括0次）如下操作：

- 如果两名同学相邻，并且他们的身高之差不超过 D，那么老师就能交换他俩的顺序。

请你帮张老师算一算，通过以上操作，字典序最小的所有同学（从左到右）身高序列是什么？

输入

第一行包含两个正整数 $N, D (1 \leq N \leq 10^{5}, 1 \leq D \leq 10^{9})$ 。接下去 N 行，每行一个正整数 hi (1<=hi<=109) 表示从左到右每名同学的身高。

输出

输出 N 行，第 i 行表示答案中第 i 名同学的身高。

样例输入

样例输出

提示

【样例解释】一种交换位置的过程如下： 7 7 3 6 2-> 7 7 6 3 2-> 7 7 6 2 3-> 7 6 7 2 3-> 6 7 7 2 3

【数据范围和约定】对于 10% 的数据，满足 N≤100；对于另外 20% 的数据，满足 N≤5000；对于全部数据，满足 $1 \leq N \leq 10_{5}, 1 \leq D \leq 10^{9}, 1 \leq h_{i} \leq 10^{9}$ 。

操作规则：若相邻两人高度差 ≤ D，则可以交换。

意味着：

两个人如果能通过一系列相邻交换（都满足差 ≤ D）而到达彼此位置，他们就在同一个可交换连通分量里。
每个连通分量内部的同学，可以任意排序（因为交换是可传递的）。不同分量之间不能越界交换。

贪心保证字典序最小：
- 每轮只收集能加入当前块的学生（满足极值约束）。
- 组内排序保证块内升序。
- 多轮扫描保证从左往右的块顺序也尽量靠前，得到字典序最小。
迭代 + 极值判断：
- 没有显式构建图，也没有用 DFS/BFS，但通过扫描 + 更新极值 + checked 标记，等价于找到了每个可交换连通块。
- 每个块内的学生之间可以自由交换，正是连通分量的特性。

python

import sys
input = sys.stdin.readline

N, D = map(int, input().split())
height = [int(input()) for _ in range(N)]

checked = [False] * N
remaining = N
result = []

while remaining > 0:	# 只要还有未处理的位置，就继续做一轮"收集组"
    buffer = []
    i = 0
    # 每轮从左到右尝试把可归入当前 buffer 的未处理元素标记并收集
    for i in range(N):
        if checked[i]:
            continue
        val = height[i]
        if not buffer:
            # buffer 为空时，直接加入第一个未处理元素
            buffer.append(val)
            maxh = val
            minh = val
            checked[i] = True
            remaining -= 1
            continue

        # ⚠️ “先用当前元素更新 max/min，再判断”
        maxh = max(maxh, val)
        minh = min(minh, val)

        # 若假设把 val 加入后仍满足与极值的差 ≤ D，则真正加入
        if maxh - val <= D and val - minh <= D:
            buffer.append(val)
            checked[i] = True
            remaining -= 1
        
    buffer.sort()
    result.extend(buffer)

print(*result, sep="\n")

复杂度：最坏情况接近 $O (k \cdot N + \sum | g r o u p | \log | g r o u p |)$ （k 为轮数）。每轮扫描 N 个元素，每个元素最多被加入一次。块内排序加 O(N log N)。

【林奕妃 2025fall-cs201, 环境科学与工程学院】思路：节点数N高达 10^5。如果是稠密图（例如D很小，大部分人互斥），边的数量可能达到 O(N^2)，直接建图和计算入度会超时（TLE）并超内存（MLE），所以不能建图。此题与此前最小数类似，但是多了一个交换的限制条件，因此在逐个交换使最左边的值最小时需要进行判断，若无法继续交换则放弃此处跳至下一个数字处。如此确定了最左边之后再确实左边第二个，以此类推。但如果只是快排依然无法达到时间要求，所以参考群中的思路采取基准值比较的方法。

python

import sys
sys.setrecursionlimit(200000)

def quick_sort_constrained(d, num_list):
    # 递归终止条件：列表为空
    if not num_list:
        return []

    # 1. 选取基准：队伍的第一名同学
    pivot = num_list[0]

    left = []  # 存放能排到 pivot 左边的同学
    right = []  # 存放只能排在 pivot 右边的同学

    # 初始化阻挡区间的最大值和最小值，最开始阻挡区间里只有 pivot 一个人
    max_blocker = pivot
    min_blocker = pivot

    # 2. 遍历剩下的人，进行“划分”
    for num in num_list[1:]:
        # 判断能否去左边：
        # 条件1: 必须比 pivot 小 (字典序要求)
        # 条件2: 必须能跟“阻挡组”里最高的人交换 (max_blocker - num <= d)
        # 条件3: 必须能跟“阻挡组”里最矮的人交换 (num - min_blocker <= d)
        if num < pivot and (max_blocker - num <= d) and (num - min_blocker <= d):
            left.append(num)
        else:
            right.append(num)	# 去右边，并加入“阻挡组”
            # 更新阻挡组的最值
            if num > max_blocker:
                max_blocker = num
            if num < min_blocker:
                min_blocker = num

    # 3. 递归合并结果：左边排好序 + [基准] + 右边排好序
    #return quick_sort_constrained(d, left) + [pivot] + quick_sort_constrained(d, right)
    return sorted(left) + [pivot] + quick_sort_constrained(d, right)

def solve():
    # 使用 sys.stdin.read 快速读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    try:
        N = int(next(iterator))
        D = int(next(iterator))
        # 读取剩余的 N 个身高数据
        heights = [int(next(iterator)) for _ in range(N)]
    except StopIteration:
        return

    # 调用排序函数
    result = quick_sort_constrained(D, heights)
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    solve()

【金于珑 25工学院】思路：确实有“点”超纲了。先是想了各种划分分治等等的想法，但是都没用，后面试着用贪心给出了一个解法，结果TLE。因为我的贪心需要重复遍历后几位元素，对比并顺便找到最佳的插入位置，所以我把数据结构改成了自己实现的链表来提升insert的效率（这样可以在找到插入点后方的对象后后以O（1）来插入），结果改完还是TLE，有点破防了。然后在群里看见大伙提到一个DAG，我上网了解学习了一下，知道了这题本质上是一个拓扑排序问题，抓住入度这个关键概念进行分组和组内的升序排列，最终AC。虽然代码不怎么简洁，但是能跑得动的代码就是好代码👍

python

import sys
from collections import deque

input = sys.stdin.readline

n, d = map(int, input().split())
q = deque(int(input()) for _ in range(n))

ans = []
group = [q.popleft()]
max_h = min_h = group[0]
wait = deque()

while q:
    h = q.popleft()
    if min_h + d >= h >= max_h - d:
        group.append(h)
        max_h = max(max_h, h)
        min_h = min(min_h, h)
    else:
        wait.append(h)
        max_h = max(max_h, h)
        min_h = min(min_h, h)
        if max_h - min_h > 2 * d:
            ans.extend(sorted(group))
            group.clear()
            # 回放等待区
            while wait:
                q.appendleft(wait.pop())
            max_h = min_h = q[0] if q else 0
            if q:
                group.append(q.popleft())
    # 最后阶段的结尾补全
    if not q:
        ans.extend(sorted(group))
        group.clear()
        if wait:
            while wait:
                q.appendleft(wait.pop())
            max_h = min_h = q[0]
            group.append(q.popleft())

print("\n".join(map(str, ans)))

【段子俊 25 物理学院】这次考试有进步我觉得，零基础，上次月考只写对三道，这次直接写对五道，就只有排队不会，排队我上次就看过，鏖战四时，殚精竭虑，连出三策，未尝一过，败兴而去，然后这次考试想了半个小时，就是用我最后一个方法，先将所有能排第一位的提出来，排出最小的，放在第一位，以此类推，结果还是超时，然后晚上又苦思冥想，废寝忘食，终于大悟，一言以蔽之，就是能排第一位的数一定比不能排第一位的数在结果上排在前，这样每次就可以提出一个序列，会快很多（我最开始的方法一次迭代只能排一个，而现在能排一个序列，但本质上是一样的）（判断能不能排第一位就是看这个数是否都能坐落于它前面的数的【x-d,x+d】邻域内），然后写出代码python3用224ms就过了，在统计榜里应该是非常快的，反正我没看到比我快的，真是写爽了，前面五题没什么好说的，在考场上都做出来了

python

import sys
from collections import deque

n, d = map(int, sys.stdin.readline().split())
l = deque(map(int, sys.stdin.read().split()))
out = []

while l:
    m = deque()
    p = l.popleft()
    left, right = p - d, p + d
    r = [p]
    L = len(l)  # 固定循环次数
    for _ in range(L):
        q = l.popleft()
        left = max(left, q - d)
        right = min(right, q + d)
        if right < left:
            l.appendleft(q)  # 把 q 放回去！
            break
        if left <= q <= right:
            r.append(q)
        else:
            m.append(q)
    l.extend(m)  # m 放到末尾
    r.sort()
    out.extend(r)

print('\n'.join(map(str, out)))

贪心法。从最左侧的输入高度找起，按照约束条件都找出来，加入暂存列表、排序、同时标志改为True。循环找接下来还没有入选的。

402ms

python

#  苏王捷 2300011075
N, D = map(int, input().split())
height = [0]*N
check = [False]*N
for i in range(N):
    height[i] = int(input())

height_new = []
while False in check:
    i, l = 0, len(height)
    buffer = []
    while i < l:
        if check[i]:
            i += 1
            continue
        if len(buffer) == 0:
            buffer.append(height[i])
            maxh = height[i]
            minh = height[i]
            check[i] = True
            continue

        maxh = max(height[i], maxh)
        minh = min(height[i], minh)
        if maxh-height[i] <= D and height[i]-minh <= D:
            buffer.append(height[i])
            check[i] = True
        i += 1
    buffer.sort()
    height_new.extend(buffer)

print(*height_new, sep='\n')

代码使用的 buffer 确实是一种 局部清空 技巧。这种技术在问题求解过程中，通过 逐步处理和清空局部数据，避免了不必要的全局状态存储，从而简化了算法逻辑，同时还能在一定程度上提升效率。

339ms

python

N, D = map(int, input().split())
h = [int(input()) for _ in range(N)]
used = [0] * N

while 0 in used:
    free = []
    for i in range(N):
        if used[i]:
            continue
        if not free:
            minv = h[i]
            maxv = h[i]
        else:
            if h[i] > maxv:
                maxv = h[i]
            if h[i] < minv:
                minv = h[i]

        if maxv - minv > 2*D:
            break

        if (h[i] + D >= maxv and h[i] - D <= minv):
            free.append(h[i])
            used[i] = 1
    free.sort()
    for v in free:
        print(v)

贪心：字典序最小必要第一位上最小；同时注意到有类似图的“联通”性质——与最高mx和最低mn距离都不超过d的同学可以移到最前面——将这些人放入tmp数组，进行sort排序。每次需要把放入tmp数组的人从待选列表中去除，用链表可以实现，去除只需把i的pre连到i的next上即可。

python

#徐前 25物理学院
n, d = map(int, input().split())
q = [[int(input()), i - 1, i + 1] for i in range(n)]  # hi, pre, next
start = [0]  # 用列表包一层，方便函数里改
tail = n

def remove(i):
    if i == start[0]:
        start[0] = q[i][2]
    else:
        q[q[i][1]][2] = q[i][2]
    if q[i][2] != tail:
        q[q[i][2]][1] = q[i][1]

ans = []
while start[0] != tail:
    tmp = []
    i = start[0]
    mn = mx = q[i][0]
    while i != tail:
        x = q[i][0]
        if mx - d <= x <= mn + d:
            tmp.append(x)
            nxt = q[i][2]
            remove(i)
            i = nxt
        else:
            i = q[i][2]
        mn = min(mn, x)
        mx = max(mx, x)
        if mx - mn > 2 * d:
            break
    ans.extend(sorted(tmp))

print(*ans, sep='\n')

上面这份代码里用二维数组 q[i] = [hi, pre, next] 来模拟链表，是“手工链表”了。可以用面向对象（OOP）的方式封装成一个 Node 类和一个 LinkedList 类，代码会更直观，也方便维护。下面是 OOP 风格：

python

class Node:
    def __init__(self, value, idx):
        self.value = value
        self.prev = idx - 1
        self.next = idx + 1

class LinkedList:
    def __init__(self, n):
        self.nodes = []
        for i in range(n):
            val = int(input())
            self.nodes.append(Node(val, i))
        self.start = 0
        self.tail = n  # 哨兵

    def remove(self, idx):
        """从链表中移除节点 idx"""
        node = self.nodes[idx]
        if idx == self.start:           # 删除头节点
            self.start = node.next
        else:                           # 左邻居指向右邻居
            self.nodes[node.prev].next = node.next
        if node.next != self.tail:      # 右邻居不是哨兵
            self.nodes[node.next].prev = node.prev
        # 注意：tail 永远保持 n，不要改！

    def iterate(self, d):
        """执行贪心逻辑，返回结果列表"""
        ans = []
        start, tail = self.start, self.tail
        while start != tail:
            tmp = []
            mn = mx = self.nodes[start].value
            i = start
            while i != tail:
                x = self.nodes[i].value
                if mx - d <= x <= mn + d:
                    tmp.append(x)
                    nxt = self.nodes[i].next
                    self.remove(i)
                    i = nxt
                else:
                    i = self.nodes[i].next
                mn = min(mn, x)
                mx = max(mx, x)
                if mx - mn > 2 * d:
                    break
            ans.extend(sorted(tmp))
            start, tail = self.start, self.tail
        return ans


if __name__ == "__main__":
    n, d = map(int, input().split())
    ll = LinkedList(n)
    ans = ll.iterate(d)
    print(*ans, sep='\n')

278ms。第16行：可以移到最前端的都pop掉了，剩下的pop后重新补到列表尾部，恰好实现了一轮筛选，并且剩下的保持原来的排列顺序。这样写的话，必须遍历完整。

python

from collections import deque

n, d = map(int, input().split())
h = deque(int(input()) for _ in range(n))
ans = []

while h:
    inlist = []
    max_val = h[0]
    min_val = h[0]
    
    # 一次遍历完成所有必要的计算
    for _ in range(len(h)):
        height = h.popleft()
        if abs(height - max_val) <= d and abs(height - min_val) <= d:
            inlist.append(height)
        else:
            h.append(height)
        
        if height < min_val:
            min_val = height
        if height > max_val:
            max_val = height
        
    
    ans += sorted(inlist)

print(*ans, sep='\n')

树状数组解法。

问题核心分析

1. 交换规则与限制 题目允许交换相邻的两个同学，当且仅当他们的身高差 $| h_{i} - h_{i + 1} | \leq D$ 。这实际上定义了一个不可交换的条件（即“阻塞”条件）：如果两个同学 $i$ 和 $j$ （假设 $i$ 原本在 $j$ 左边，即 $i < j$ ），且他们的身高差 $| h_{i} - h_{j} | > D$ ，那么他们永远无法交换位置。这意味着：在最终的序列中， $h_{i}$ 必须依然排在 $h_{j}$ 的前面。

2. 转化为有向无环图 (DAG) 的拓扑排序 我们可以将这个问题看作是一个图论问题：

节点：每个位置上的同学。
有向边：对于任意一对 $(i, j)$ ，如果 $i < j$ 且 $| h_{i} - h_{j} | > D$ ，则存在一条从 $i$ 指向 $j$ 的边（代表 $i$ 必须在 $j$ 之前）。
目标：在满足所有这些前后限制的情况下，求字典序最小的序列。这本质上是求这个 DAG 的字典序最小的拓扑排序。

3. 为什么使用“分层”算法？ 直接建图边的数量可能高达 $O (N^{2})$ ，对于 $N = 10^{5}$ 来说会超时。我们需要一种更高效的方法来隐式地处理这些边。代码中使用了一种基于“层数” (Layer) 的动态规划思想：

定义 $L a y e r (i)$ 为第 $i$ 个同学在逻辑上必须处于的“批次”。
如果 $i$ 被左边的某个 $k$ 阻塞（即 $| h_{k} - h_{i} | > D$ ），那么 $i$ 必须排在 $k$ 后面。
转移方程： $L a y e r (i) = 1 + max ({L a y e r (k) ∣ k < i, | h_{k} - h_{i} | > D} \cup {0})$ 。
换句话说， $i$ 的层数等于所有能“挡住”它的左侧同学中最大的层数加 1。

4. 同层性质 同一个 $L a y e r$ 内的所有同学，彼此之间一定满足 $| h_{a} - h_{b} | \leq D$ 。如果他们之间有阻塞关系，他们就不可能在同一层。既然同层内没有阻塞关系（即可以两两交换），为了使字典序最小，我们只需要将每一层的同学按身高从小到大排序输出即可。

代码逻辑详细解读

代码通过树状数组 (Fenwick Tree / BIT) 来高效维护和查询区间的最大层数。

1. 数据离散化

由于身高 $h_{i}$ 高达 $10^{9}$ ，不能直接用作数组下标。

python

vals = sorted(set(h))
M = len(vals)
rank = {v: i for i, v in enumerate(vals)} # 将身高映射到 0 ~ M-1

这一步将身高映射为相对排名（Rank），用于在树状数组中定位。

2. 树状数组 (Fenwick Tree) 的作用

代码定义了 bit_update 和 bit_query，用于维护前缀最大值。我们需要两棵树状数组：

bitL: 维护正向的身高。用于查询身高小于 $h_{i} - D$ 的那些同学中，最大的层数是多少。
bitR: 维护反向的身高。用于查询身高大于 $h_{i} + D$ 的那些同学中，最大的层数是多少。

3. 核心循环：计算每个同学的 Layer

遍历每个同学的身高 hi：

查找左侧阻塞者 (Small Blockers)：我们需要找左侧身高在区间 $(- \infty, h_{i} - D - 1]$ 范围内的最大层数。
python
```
L = bisect.bisect_left(vals, hi - D)
left_max = bit_query(bitL, L) if L > 0 else 0
```
bitL 存储的是以身高 Rank 为索引的层数最大值。bisect 找到了对应的离散化边界。
查找右侧阻塞者 (Large Blockers)：我们需要找左侧身高在区间 $[h_{i} + D + 1, + \infty)$ 范围内的最大层数。
python
```
R = bisect.bisect_right(vals, hi + D)
if R < M:
    posR = M - R # 注意这里：为了用前缀最大值的BIT查后缀，用了 M - index
    right_max = bit_query(bitR, posR)
```
bitR 使用了一个技巧：它将身高倒过来映射。查询 bitR 的前缀实际上是在查询原身高的后缀（即大数值部分）。

计算当前层数并存储：

python

cur_layer = max(left_max, right_max) + 1
max_layer = max(max_layer, cur_layer)
layer_buckets.setdefault(cur_layer, []).append(hi)

算出层数后，将该身高放入对应的桶（Bucket）中。

更新树状数组：将当前同学的身高和计算出的层数更新进 bitL 和 bitR，让他成为后续同学的潜在阻塞者。
python
```
s = rank[hi]
bit_update(bitL, s + 1, cur_layer)
bit_update(bitR, M - s, cur_layer)
```

4. 输出答案

python

for layer in range(1, max_layer + 1):
    if layer in layer_buckets:
        for v in sorted(layer_buckets[layer]):
            out_lines.append(str(v))

按层号从小到大遍历，对于每一层内部，按身高从小到大排序（贪心，字典序最小），拼接成结果输出。

算法复杂度

离散化: $O (N \log N)$ (排序)。
计算层数: 对每个元素进行 BIT 查询和更新。BIT 操作是 $O (\log N)$ ，共 $N$ 次。总计 $O (N \log N)$ 。
输出排序: 相当于对数组进行了分块排序，最坏情况也是 $O (N \log N)$ 。

总时间复杂度: $O (N \log N)$ 。这足以通过 $N = 10^{5}$ 的数据范围（通常 Python 需要控制在 1-2秒内，这个算法非常高效）。

样例演练

输入：5 3，序列 7 7 3 6 2

7: 左边没数。 $L a y e r = 1$ 。bit更新: 7的位置存1。桶: {1: [7]}
7: 左边 7，差0 (<=3)，不阻塞。 $L a y e r = 1$ 。bit更新: 7的位置存1。桶: {1: [7, 7]}
3: 左边有 7, 7。
- $7 > 3 + 3$ ? 是 ( $7 > 6$ )。被7阻塞。
- 查得7的层数是1。
- $L a y e r = 1 + 1 = 2$ 。桶: {1: [7,7], 2: [3]}
6: 左边有 7(L1), 7(L1), 3(L2)。
- $| 7 - 6 | = 1 \leq 3$ (不阻塞)。
- $| 3 - 6 | = 3 \leq 3$ (不阻塞)。
- 没有被阻塞。 $L a y e r = 1$ 。桶: {1: [7,7,6], 2: [3]}
2: 左边有 7(L1), 6(L1), 3(L2)...。
- $7 > 2 + 3$ (阻塞，MaxLayer=1)。
- $6 > 2 + 3$ (阻塞，MaxLayer=1)。
- $3$ 不阻塞 (差1)。
- 最大阻塞层数是1，所以 $L a y e r = 1 + 1 = 2$ 。桶: {1: [7,7,6], 2: [3,2]}

最终处理:

Layer 1: [7, 7, 6] -> 排序 -> 6, 7, 7
Layer 2: [3, 2] -> 排序 -> 2, 3
合并: 6 7 7 2 3 (与样例输出一致)。

python

import sys
import bisect

# 增加递归深度限制（虽然本解法主要通过迭代实现，这在大规模数据下是好习惯）
sys.setrecursionlimit(200000)

def solve():
    # 使用 sys.stdin.read 一次性读取所有输入，显著提升 Python I/O 速度
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        N = int(next(iterator))
        D = int(next(iterator))
        # 读取 N 个同学的身高
        h = [int(next(iterator)) for _ in range(N)]
    except StopIteration:
        return

    # --- 1. 离散化 (Coordinate Compression) ---
    # 身高数值范围很大 (1e9)，不能直接作为数组下标。
    # 但 N 只有 1e5，所以将其映射到 [0, M-1] 的排名 (Rank)。
    vals = sorted(list(set(h)))
    rank_map = {v: i for i, v in enumerate(vals)}
    M = len(vals)

    # --- 2. 定义树状数组 (Fenwick Tree) ---
    # bitL: 用于查询值域 [0, val - D - 1] 内的最大层数
    # bitR: 用于查询值域 [val + D + 1, max_val] 内的最大层数
    # 数组大小设为 M + 1 (因为树状数组通常使用 1-based 索引)
    bitL = [0] * (M + 1)
    bitR = [0] * (M + 1)

    # 单点更新：将 idx 位置的值更新为 val（取最大值）
    def bit_update(bit, idx, val):
        limit = len(bit)
        while idx < limit:
            if val > bit[idx]:
                bit[idx] = val
            idx += idx & (-idx)

    # 前缀查询：查询 [1, idx] 范围内的最大值
    def bit_query(bit, idx):
        res = 0
        while idx > 0:
            if bit[idx] > res:
                res = bit[idx]
            idx -= idx & (-idx)
        return res

    # --- 3. 计算每个同学的层数 ---
    # layer_buckets 用于收集每一层的同学身高
    # 字典结构：{层数: [身高1, 身高2, ...]}
    layer_buckets = {}
    max_layer_global = 0

    for val in h:
        r = rank_map[val] # 获取当前身高的离散化排名 (0 ~ M-1)
        
        # --- 计算左侧阻塞的最大层数 ---
        
        # 情况 A: 被身高太小的人阻塞 (h_k < val - D)
        # bisect_left 找到第一个 >= val-D 的位置，其左侧即为 < val-D
        idx_small = bisect.bisect_left(vals, val - D)
        # 查询 bitL 在范围 [0, idx_small-1] 的最大层数 (对应BIT下标 idx_small)
        max_L = bit_query(bitL, idx_small)
        
        # 情况 B: 被身高太大的人阻塞 (h_k > val + D)
        # bisect_right 找到第一个 > val+D 的位置，该位置及右侧即为 > val+D
        idx_large = bisect.bisect_right(vals, val + D)
        
        # 在 bitR 中，我们使用反转映射技巧：
        # 实际排名 rank 越大，映射到 bitR 的下标 M - rank 越小。
        # 这样查询 bitR 的前缀最大值，实际上就是查询原数组的后缀最大值。
        # 范围 [idx_large, M-1] 映射到 bitR 下标 [1, M - idx_large]
        max_R = 0
        if idx_large < M:
            pos_in_bitR = M - idx_large
            max_R = bit_query(bitR, pos_in_bitR)
            
        # 当前同学的层数 = 所有阻塞者中的最大层数 + 1
        cur_layer = max(max_L, max_R) + 1
        
        # 记录全局最大层数以便后续输出
        if cur_layer > max_layer_global:
            max_layer_global = cur_layer
        
        # 将身高放入对应的层桶中
        if cur_layer not in layer_buckets:
            layer_buckets[cur_layer] = []
        layer_buckets[cur_layer].append(val)
        
        # --- 更新树状数组 ---
        # 将当前同学的信息加入 BIT，成为后续同学可能的阻塞者
        
        # 更新 bitL: 正常映射，下标为 r + 1
        bit_update(bitL, r + 1, cur_layer)
        
        # 更新 bitR: 反转映射，下标为 M - r
        bit_update(bitR, M - r, cur_layer)

    # --- 4. 输出结果 ---
    # 字典序最小原则：
    # 1. 必须按层数从小到大输出 (拓扑序)
    # 2. 同一层内互不阻塞，按身高从小到大输出 (贪心)
    
    output = []
    for layer in range(1, max_layer_global + 1):
        if layer in layer_buckets:
            # 对该层的所有身高进行排序
            members = sorted(layer_buckets[layer])
            for v in members:
                output.append(str(v))
    
    sys.stdout.write('\n'.join(output) + '\n')

if __name__ == '__main__':
    solve()

【23级郭绍阳】线段树

排队-题解，https://www.cnblogs.com/guoshaoyang/p/17824372.html

思路：这道题一直想不出来，豆包、deepseek、Gemini和GPT也被干趴下了，后来在网上搜到了别人题解的链接，底层思路还是用到了线段树的区间查询与单点修改性质，用得非常巧妙，之后还要多体会参悟一下。

python

class SegmentTreeNode:
    def __init__(self, start, end, val):
        self.start = start
        self.end = end
        self.val = val
        self.lson = None
        self.rson = None


class SegmentTree:
    def __init__(self, start, end):
        self.root = SegmentTreeNode(start, end, 0)
        self.start = start
        self.end = end

    def modify(self, node, pos, value, start=None, end=None):
        if (start is None):
            start, end = self.start, self.end
        if (node is None):
            node = SegmentTreeNode(start, end, value)
        if (start == end):
            node.val = max(node.val, value)
            return node
        mid = (node.start + node.end) // 2
        if pos <= mid:
            node.lson = self.modify(node.lson, pos, value, start, mid)
        else:
            node.rson = self.modify(node.rson, pos, value, mid + 1, end)
        node.val = max(node.val, value)
        return node

    def query(self, node, qstart, qend):
        if ((node is None) or qstart > node.end or qend < node.start):
            return 0
        if (qstart <= node.start and node.end <= qend):
            return node.val
        ret = max(self.query(node.lson, qstart, qend), self.query(node.rson, qstart, qend))
        return ret


N, D = map(int, input().split())
h = [int(input()) for _ in range(N)]

MAXH = max(h)
layers = SegmentTree(1, MAXH)
members = [[]]
for hi in h:
    current_layer = max(layers.query(layers.root, 1, hi - D - 1), layers.query(layers.root, hi + D + 1, MAXH)) + 1
    if (current_layer >= len(members)):
        members.append([])
    members[current_layer].append(hi)
    layers.modify(layers.root, hi, current_layer)

for layer in members:
    for _ in sorted(layer):
        print(_)

上面 Python 代码思路（求每个元素的最长阻挡链长度，即层数）是正确的，但在 Python 中直接使用基于类（Class）和动态开点的线段树会导致严重的性能问题，主要体现在以下几点：

内存与对象创建开销：SegmentTreeNode 类的实例化开销在 Python 中很大。当 $N = 10^{5}$ 时，创建几十万个对象会导致 TLE（Time Limit Exceeded）甚至 MLE。
值域过大：题目中 $H_{i}$ 可达 $10^{9}$ 。如果不进行离散化，直接在 $[1, 10^{9}]$ 上建树，虽然动态开点能节省空间，但递归深度（约 30 层）叠加 Python 的函数调用开销，速度非常慢。
I/O 速度：input() 和 print() 在大量数据下由于 I/O 缓冲问题会很慢。

优化方案

为了通过这道题，需要进行以下优化：

离散化 (Coordinate Compression)：虽然身高 $H_{i}$ 很大，但总共只有 $N$ 个身高。我们可以将所有出现过的身高排序去重，映射到 $0, 1, \dots, m$ 的小范围内。这样就可以使用固定大小的数组来代替动态树。
数组版线段树 (Array-based Segment Tree)：抛弃 class 结构，使用扁平的数组 tree = [0] * (4 * N) 来存储线段树。这能极大减少内存占用和访问时间。
迭代式线段树 (zkw线段树)：使用非递归（循环）的方式实现查询和更新，避免 Python 的递归深度限制和函数调用开销，速度通常比递归快一倍以上。
快速 I/O：使用 sys.stdin.read 一次性读取所有输入。

优化后的代码

python

import sys
import bisect

# 设置递归深度，虽然下面的实现是迭代的，但在混合解法中是个好习惯
sys.setrecursionlimit(200000)

def solve():
    # 1. 快速输入
    input = sys.stdin.read
    data = input().split()
    
    iterator = iter(data)
    try:
        N = int(next(iterator))
        D = int(next(iterator))
    except StopIteration:
        return

    h = []
    for _ in range(N):
        h.append(int(next(iterator)))

    # 2. 离散化 (Discretization)
    # 将 10^9 的身高映射到 0..N 的排名上
    sorted_h = sorted(list(set(h)))
    m = len(sorted_h)
    
    # 3. 建立迭代式线段树 (Array-based Iterative Segment Tree)
    # 树的大小只需覆盖离散化后的长度 m
    # 这里的 size 最好是 2 的幂次或者是 m+1，数组大小开 2*size 即可
    size = m + 1
    tree = [0] * (2 * size)

    # 单点更新：将位置 pos 的值更新为 max(当前值, val)
    def update(pos, val):
        pos += size  # 移动到叶子节点位置
        if tree[pos] < val:
            tree[pos] = val
            while pos > 1:
                pos >>= 1  # 移动到父节点
                # 父节点的值是两个子节点的最大值
                tree[pos] = max(tree[2*pos], tree[2*pos+1])

    # 区间查询：查询 [l, r] 闭区间内的最大值
    def query(l, r):
        if l > r:
            return 0
        l += size
        r += size
        res = 0
        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 >>= 1
            r >>= 1
        return res

    # 4. 计算每位同学的层数 (Layer)
    # members[k] 存储第 k 层的所有身高
    members = [] 

    for val in h:
        # 我们需要查询原值域范围：(-inf, val - D - 1] 和 [val + D + 1, +inf)
        
        # 利用 bisect 在离散化数组中找到对应的排名范围
        # limit_low: val - D - 1 在 sorted_h 中的右边界索引
        # bisect_right 返回插入位置，插入位置左边的元素都 <= limit_low
        limit_low = val - D - 1
        idx_low = bisect.bisect_right(sorted_h, limit_low) - 1
        
        # limit_high: val + D + 1 在 sorted_h 中的左边界索引
        # bisect_left 返回插入位置，该位置及右边的元素都 >= limit_high
        limit_high = val + D + 1
        idx_high = bisect.bisect_left(sorted_h, limit_high)
        
        # 当前值的排名（用于更新）
        rank_val = bisect.bisect_left(sorted_h, val)

        # 查询两个区间的最大层数
        # 区间1: [0, idx_low]
        # 区间2: [idx_high, m-1]
        max_f = 0
        
        if idx_low >= 0:
            q1 = query(0, idx_low)
            if q1 > max_f: max_f = q1
            
        if idx_high < m:
            q2 = query(idx_high, m - 1)
            if q2 > max_f: max_f = q2
            
        current_layer = max_f + 1
        
        # 更新线段树
        update(rank_val, current_layer)
        
        # 将该身高加入对应的层
        # 动态扩展 members 数组
        if current_layer > len(members):
            for _ in range(current_layer - len(members)):
                members.append([])
        
        members[current_layer - 1].append(val)

    # 5. 输出结果
    # 每一层内部按字典序排序（从小到大），因为层内互不干扰（或者说已被分层逻辑处理）
    output = []
    for layer in members:
        layer.sort()
        output.extend(layer)
        
    print('\n'.join(map(str, output)))

if __name__ == '__main__':
    solve()

代码关键点解释：

bisect 的妙用：原问题是基于数值的范围查询（例如 query(1, h[i] - D - 1)），但线段树是基于离散化后的下标构建的。
- bisect_right(sorted_h, val - D - 1) 能够快速找到数值 val - D - 1 在排序数组中对应的下标边界，从而将“数值区间”转化为“下标区间” [0, idx_low]。
- 这样我们既保留了数值的大小关系（ $D$ 的限制），又享受了小范围下标带来的线段树效率。
扁平化与位运算： tree 数组的大小仅为 $2 \times (N 的去重个数 + 1)$ 。
- 对于节点 i，左孩子是 2*i，右孩子是 2*i+1（或者在位运算中 i<<1 和 i<<1|1）。
- 这种写法在 Python 中比类对象的属性访问快得多。
逻辑一致性：你的贪心策略（计算层数 -> 层内排序）是完全正确的。这个算法本质上是计算最长反链（或者说在特定偏序关系下的拓扑层级），同一层的元素之间没有强制的先后依赖关系（或者依赖关系已被打破），因此为了字典序最小，层内应当从小到大输出。

总结记忆口诀

bisect.bisect_left 和 bisect.bisect_right 的区别和用法。

函数	行为
`bisect_left(a, x)`	返回第一个 ≥ x 的位置
`bisect_right(a, x)`	返回第一个 > x 的位置

只要记住这个核心规则，就能应对所有场景！

python

import bisect

a = [1, 2, 3, 3, 3, 5, 6]

left_index = bisect.bisect_left(a, 3)
right_index = bisect.bisect_right(a, 3)

print("列表:", a)
print("bisect_left(a, 3) =", left_index)   # 输出: 2
print("bisect_right(a, 3) =", right_index) # 输出: 5

"""
总结记忆口诀: 函数	行为
bisect_left(a, x)	返回 第一个 ≥ x 的位置
bisect_right(a, x)	返回 第一个 > x 的位置
"""

下面这个代码在这组数据下不对。但是交到OJ上居然能过。

会输出

python

from collections import deque

n, d = map(int, input().split())
h = deque(int(input()) for _ in range(n))

ans = []
while h:
    inlist = []
    # 用队首初始化当前块的最小/最大值
    cur_min = cur_max = h[0]

    # 这一轮完整扫一遍剩余同学
    for _ in range(len(h)):
        x = h.popleft()

        # 能否并入当前“可自由重排”的集合：
        # 条件等价于并入后整体直径 <= D
        if abs(x - cur_min) <= d and abs(x - cur_max) <= d:
            inlist.append(x)
        else:
            # 放回队尾，下轮再处理
            h.append(x)

        # 无论收不收，这一轮的“已见元素”极值都要更新
        # （关键！保持与原 AC 思路一致）
        if x < cur_min: cur_min = x
        if x > cur_max: cur_max = x
        if cur_max - cur_min > 2*d:
            break

    # 这一轮收集到的集合内部可以任意排序，取最小字典序=>升序
    inlist.sort()
    ans.extend(inlist)

print(*ans, sep="\n")

不变量 1： 若两人身高差 > D，则他们的相对先后次序永远无法互换（哪怕中间人再多，想要换序必然要相邻一次，而那次不允许交换）。

不变量 2： 对于任意集合 S，若 max⁡(S)−min⁡(S)≤D，则 S 内任意两人都可相邻交换，因而集合内部可任意重排。

本算法每一轮从队首值出发，尽可能扩张一个“直径 ≤ D”的集合（inlist）。

对于被拒的元素 y：此时已收集合有某个元素 x 使 ∣x−y∣>D。于是 y 过不去整个已收集合，必然在最终答案中排在它们之后——把 y 旋到队尾，正是“延后处理”。
对于被收的元素，因集合直径 ≤ D，它与集合内所有人都能两两交换，可被放到前缀的任意位置；取升序即可得到该轮能放到最前的一段的最小字典序。

完成一轮后，剩余元素重复同样过程；由于所有“过不去”的人都被延后，最终得到的整体序列是满足所有“不可逆对”（差>D）顺序约束下的最小字典序。

【林家卫 25物理学院】思路：每一次循环中，从前往后找到所有可以一路移到最前面的人，这些人都可以移到最前面，并且他们之间也可以互相任意交换，如此循环往复即可完成。这个方法的最差时间复杂度是 $O (n^{2})$ ， $n = 10^{5}$ 的数据量应该是过不了的，但是由于数据比较弱，没想到竟然过了

python

n, d = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

origin = h
while origin:
    m = 1000000000
    M = 0
    new = []
    out = []
    for x in origin:
        if x > m + d or x < M - d:
            new.append(x)
        else:
            out.append(x)
        m = min(m, x)
        M = max(M, x)
    out.sort()
    for x in out:
        print(x)
    origin = new

【徐前 25 物理学院】思路：贪心：字典序最小必要第一位上最小；同时注意到有类似图的“联通”性质——与最高mx和最低mn距离都不超过d的同学可以移到最前面——将这些人放入tmp数组，进行sort排序。每次需要把放入tmp数组的人从待选列表中去除，用链表可以实现，去除只需把i的pre连到i的next上即可。学习了同学的优化想法以后，可以把每次更新的tmp数组按指标存储，从前往后依次表示每个等价类，mx,mn数组存储每个等价类的最大值最小值。这样就可以一次遍历整个数组，找每个元素所属的等价类

链表优化改进了OOP写法

python

class Node:
    def __init__(self, value, idx):
        self.value = value
        self.pre = idx - 1
        self.next = idx + 1

class LinkedList:
    def __init__(self, n):
        self.nodes = []
        #h = list(map(int, input().split()))
        for i in range(n):
            val = int(input())
            self.nodes.append(Node(val, i))
        self.start = 0
        self.tail = n

    def remove(self, idx):
        node = self.nodes[idx]
        if idx == self.start:
            self.start = node.next
        else:
            self.nodes[node.pre].next = node.next
            if node.next == self.tail:
                self.tail = idx
            else:
                self.nodes[node.next].pre = node.pre

    def solve(self, d):
        ans = []
        while self.start != self.tail:
            tmp = []
            i = self.start
            mn = mx = self.nodes[i].value

            while i != self.tail:
                x = self.nodes[i].value
                nxt = self.nodes[i].next
                if mx - d <= x <= mn + d:
                    tmp.append(x)
                    self.remove(i)

                mn = min(mn, x)
                mx = max(mx, x)
                if mx - mn > 2 * d:
                    break
                i = nxt

            ans.extend(sorted(tmp))

        return ans

# main
n, d = map(int, input().split())
q = LinkedList(n)
result = q.solve(d)

print(*result, sep='\n')

25353: 排队 ​

25353: 排队