社区讨论
求助过不了编
灌水区参与者 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 条回复,欢迎继续交流。
正在加载回复...