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有快读操作吗?