27093: 排队又来了

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

内存 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: 排队又来了