摘要
Title: 788. 逆序对的数量
Tag: 归并排序、逆序对、树状数组
Memory Limit: 64 MB
Time Limit: 1000 ms

788. 逆序对的数量

题意

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
思路

代码

2022.3.24 更新

ans = 0
def merge(l, r):
    global ans
    if l >= r:
        return 
    mid = l + r >> 1
    merge(l, mid)
    merge(mid + 1, r)
    tmp = []
    i, j = l, mid + 1
    while i <= mid or j <= r:
        if j == r + 1 or i <= mid and a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            ans += (mid - i + 1)
            tmp.append(a[j])
            j += 1
    a[l: r + 1] = tmp

n = int(input())
a = list(map(int, input().split()))

merge(0, n - 1)
print(ans)

所以这样也可以，用总的数对减去正序对（包括相等的），也就是逆序对

'''
Author: NEFU AB-IN
Date: 2022-02-18 15:25:02
FilePath: \ACM\Acwing\788.py
LastEditTime: 2022-02-18 15:48:43
'''

a = []


def merge(l, r):
    if l >= r:
        return 0
    mid = l + r >> 1
    res = merge(l, mid) + merge(mid + 1, r)

    i, j = l, mid + 1
    tmp = []

    while i <= mid and j <= r:
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
            res += r - j + 1
        else:
            tmp.append(a[j])
            j += 1
    tmp += a[i:mid + 1]
    tmp += a[j:r + 1]
    a[l:r + 1] = tmp
    return res


n = int(input())
a = list(map(int, input().split()))

print(n * (n - 1) // 2 - merge(0, n - 1))

树状数组求逆序对
更新于 2023.3.26

所以规律如下：(x代表a[i]在离散化数组中二分出的下标)
[比我小] ： $sum(x-1)$
[小于等于我] : $sum(x)$
[比我大] : $i-sum(x)$ (逆序对)
[大于等于我] : $i-sum(x-1)$

from bisect import bisect_left
from copy import deepcopy

N = int(1e5 + 10)
INF = int(1e18)
tr = [0] * N

def lowbit(x): return x & -x

def add(x, d):
    while x < N:
        tr[x] += d
        x += lowbit(x)

def query(x):
    res = 0
    while x > 0:
        res += tr[x]
        x -= lowbit(x)
    return res

n = int(input())
a = list(map(int, input().split()))

a = [-INF, *a]
xs = deepcopy(a)

xs = sorted(list(set(xs)))

ans = 0
for i in range(1, n + 1): #下标要从1开始，故在原数组和离散化数组前面都加一个哨兵
    x = bisect_left(xs, a[i])
    add(x, 1)
    ans += (i - query(x))

print(ans)

788. 逆序对的数量

题意

思路

代码