社区讨论

求助过不了编

灌水区参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lv22f3ku
此快照首次捕获于
2024/04/16 15:31
2 年前
此快照最后确认于
2024/04/16 18:54
2 年前
查看原帖
PYTHON
N = int(1e5 + 10)
INF = int(1e9 + 10)
L = [int(0) for i in range(N)]
R = [int(0) for i in range(N)]
t = [-INF for i in range(N)]
a = [int(0) for i in range(N)]

def Max(a, b):
    if a > b:
        return a
    return b

def cmp(a, b):
    if a[0] > b[0]:
        return a
    return b

def build(p, l, r):
    L[p] = int(l), R[p] = int(r)
    if l == r:
        t[p] = a[l]
        return
    mid = int((l + r) // 2)
    if l <= mid:
        build(p * 2, l, mid)
    if r > mid:
        build(p * 2 + 1, mid + 1, r)
    t[p] = Max(t[p * 2]. t[p * 2 + 1])

def change(p, x, v):
    if L[p] == R[p]:
        t[p] = v
        return
    mid = int((l + r) // 2)
    if x <= mid:
        change(p * 2, x, v)
    if x > mid:
        change(p * 2 + 1, x, v)
    t[p] = Max(t[p * 2], t[p * 2 + 1])

def ask(p, l, r):
    if l <= L[p] and r >= R[p]:
        return [t[p], p]
    mid = int((l + r) // 2)
    val = [-INF, p]
    if l <= mid:
        val = cmp(val, ask(p * 2, l, r))
    if r > mid:
        val = cmp(val, ask(p * 2 + 1, l, r))
    return val

n = int(input())
for i in range(n):
    b = input()
    a[i + 1] = int(b)
build(int(1), int(1), n)
ans = [int(0) for i in range(N)]
for i in range(n):
    val = ask(int(1), int(1), n)
    ans[i] = val[0], change(1, val[1], -INF)
for i in range(n):
    print(ans[i], end = ' ')
print("\n")

写的是线段树,不太会 python,build 里面第一行错了,求教

回复

1 条回复,欢迎继续交流。

正在加载回复...