python为什么拉跨了

P1908 逆序对

LightString @ 2020-10-18 20:44:56

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)

by LightString @ 2020-10-18 20:45:44

数据更新之后为什么python全死光了,是不是某些内置操作效率有毒?


by _5011_ @ 2020-10-18 20:47:22

可能是读入太慢?


by LightString @ 2020-10-18 21:01:47

@Zephyr_ 那python有快读操作吗?


|