AcWing 1265. 数星星 PY3
原题链接
中等
作者:
徐枫月丶
,
2024-03-27 00:13:38
,
所有人可见
,
阅读 2
'''
这道题表面上看起来可以用一维的静态前缀和完成 但实际上 因为y大的x不一定大
所以全部读入再计算前缀和 会导致答案超出 因此必须动态查询 使用树状数组
'''
n = int(input())
X = 32010
stars, ans = [0] * X, [0] * n
def lowbit(x):
return -x & x
def add(x: int):
i = x
while i < X:
# add相当于在当前位置+1⭐
stars[i] += 1
i += lowbit(i)
def query(x: int):
i, pp = x, 0
while i > 0:
pp += stars[i]
i -= lowbit(i)
return pp
for i in range(n):
x, y = map(int, input().split())
add(x + 1)
test = query(x + 1)
# print(test)
# 前缀和计算star时会计算到自身 所以要把计算出来的ans-1
ans[test - 1] += 1
for i in ans:
print(i)