python - 计数反转而无需重复两次

这个问题可以找到here。
这是我试过的，但我得到了错误的答案。我的逻辑是这样的。在任何时刻，如果排序队列和状态队列中的位置差为负值，则将该差的绝对值加入混沌。现在，如果我面对两个连续的正差分，并且前一个位置的数字大于状态队列中的当前数字，我将混沌加上1。

def minimumBribes(q):
    truth = None
    old = 0
    chaos = 0
    for i in range(len(q)):
        diff = (i+1)-q[i]
        if diff < -2:
            print("Too chaotic")
            return

        if diff < 0 :
            chaos = chaos + abs(diff)
            truth = True
            continue
        else:
            if truth == True:
                truth = False
                old = q[i]
                continue
            if old > q[i]:
                chaos = chaos + 1


        old = q[i]
    print(chaos)

最佳答案

用比较法计算线性时间上的倒数是不可能的。这在理论上是有限度的。https://cs.stackexchange.com/questions/74515/can-we-count-the-number-of-inversions-in-time-mathcalon
您可以使用fenwick树（也称为二叉索引树）来解决它。这个想法在这里描述（https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/）。