python树状数组 50

浮梦CalcuLus @ 2021-09-14 12:44:04

c = [0 for i in range(500005)]
n = 0
def lowbit(x):
    return x & (-x)
def add(x, k, n):
    while k <= n:
        c[k] += x
        k += lowbit(k)
def getsum(x):
    ret = 0
    while x > 0:
        ret += c[x]
        x -= lowbit(x)
    return ret

d = {}
n = int(input())
a = list(map(int, input().split()))
cnt = 1
b = sorted(a)
for i in range(n):
    if b[i] not in d:
        d[b[i]] = cnt
        cnt += 1
a = list(map(lambda x: d[x], a))
ans = 0
for i in range(n):
    num = a[i]
    ans += i - getsum(num)
    add(1, num, n)
print(ans)

by 404Not_Found @ 2021-09-14 13:05:34

py常数原因吧？

by 404Not_Found @ 2021-09-14 13:07:30

import sys
n = int(input())
class Ww(object):
    def __init__(self,pos,val):
        self.pos=pos
        self.val=val
    def __repr__(val,):
        return (val,)
a=[Ww(i+1,0) for i in range(n)]
b=sys.stdin.readline().split()
for i in range(n):
    a[i].val=int(b[i])
t=[0 for i in range(n+1)]
def lowbit(x):
    return x&-x
def ad(x,k):
    while x<=n:
        t[x]+=k
        x+=lowbit(x)
def que(x):
    res=0
    while x>0:
        res+=t[x]
        x-=lowbit(x)
    return res

a=sorted(a,key = lambda Ww: -Ww.val)
ans=0
for i in range(n):
    ad(a[i].pos,1)
    ans+=que(a[i].pos-1)
print(ans)

提交记录翻出来的AC代码，应该不算侵权吧

by 404Not_Found @ 2021-09-14 13:16:58

是不是这里的原因?

if b[i] not in d:

50 分是 O(n^2) 的暴力分，not in 的时间复杂度可能是 O(n) 的。

本人不是很懂 py,就参考一下吧

by 404Not_Found @ 2021-09-14 13:19:09

@浮梦CalcuLus

by 浮梦CalcuLus @ 2021-09-14 16:18:19

@404Not_Found 谢谢聚聚我回头想想怎么改

by 浮梦CalcuLus @ 2021-09-14 16:42:29

@404Not_Found 但是我刚刚查了字典里面的in是O(1)的 按理来说不应该啊

by okok8260 @ 2022-03-13 16:29:28

@404Not_Found

这个代码我用 11 号数据点试了一下, 运行了 1.9s, 而且答案是错的...

@浮梦CalcuLus 的代码运行了 1.7s, 比那个"AC"代码还快, 而且答案是对的.

应该就是单纯的数据加强了, 所以 py 性能跟不上了

by okok8260 @ 2022-03-13 16:53:05

跑了一下 profile, 主要耗时长这样, 很难降了...

我把 lowbit 函数改成 inline 试了下, 降了 0.3s, 现在是 1.4s, 降不下来了...