AcWing 4721. 排队(离散化树状数组)
原题链接
困难
python3 代码
def main():
n = int(input())
h = list(map(int, input().split()))
a, ans = sorted(list(set(h))), [-1] * n
m = len(a)
tree = [-1] * (m+5)
def getId(x: int) -> int:
left, right = 0, m-1
while left < right:
mid = left+right >> 1
if a[mid] >= x: right = mid
else: left = mid+1
return left+2
def query(u: int) -> int:
res = -1
while u:
res = max(res, tree[u])
u -= u & -u
return res
def update(u: int, v: int) -> int:
while u < len(tree):
tree[u] = max(tree[u], v)
u += u & -u
for i in range(n-1, -1, -1):
q = query(getId(h[i])-1)
if q != -1:
ans[i] = q-i-1
update(getId(h[i]), i)
for e in ans:
print(e, end = " ")
if __name__ == '__main__':
main()