社区讨论

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 条回复,欢迎继续交流。

正在加载回复...