社区讨论
python为什么拉跨了
P1908逆序对参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lod3hjoq
- 此快照首次捕获于
- 2023/10/31 00:08 2 年前
- 此快照最后确认于
- 2023/11/05 10:26 2 年前
PYTHON
class BIT: #Binary Indexed Tree
__c = [0]
def __init__(self, n):
self.__c *= n + 2
def __lowbit(self, x):
return x & (-x)
def Add(self, pos, x):
while pos < len(self.__c):
self.__c[pos] += x
pos += self.__lowbit(pos)
def Sum(self, pos):
ans = 0
while pos > 0:
ans += self.__c[pos]
pos -= self.__lowbit(pos)
return ans
n = int(input())
a = list(map(int, input().split()))
tmp = a[:]
tmp.sort()
h = {}
for i in range(n):
h[tmp[i]] = i + 1
tree = BIT(n)
ans = 0
for i in range(n-1, -1, -1):
tree.Add(h[a[i]], 1)
ans += tree.Sum(h[a[i]] - 1)
print(ans)
回复
共 3 条回复,欢迎继续交流。
正在加载回复...