思路：树状数组

树状数组模板题，即用树状数组来统计逆序对数量

对于位置$i$，我们只需要去考虑左边比它大的元素个数，然后累加，即为整个数组的逆序对数量，记为$res$

对于第$i$个数字取反之后，左边所有的数字都会比它大，因此会增加$i-1$个逆序对

然后我们需要统计右边有多少逆序对被消除了，即统计右边比$w[i]$小的数字的个数，然后把它去掉即可，同样使用树状数组维护即可

Python

def lbt(x):
    return x & -x

def get(x, a):
    res = 0
    i=x
    while i>0:
        res += a[i]
        i-=lbt(i)
    return res

def fix(x, a):
    i = x
    while i < len(a):
        a[i] += 1
        i += lbt(i)

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] * (n+1)
tr1 = [0] * (n+1)
tr2 = [0] * (n+1)
ans = 0
for i in range(1, n+1):
    val = get(n, tr1) - get(a[i], tr1)
    ans += val
    b[i] += val
    fix(a[i], tr1)
for i in range(n, 0, -1):
    b[i] += get(a[i], tr2)
    fix(a[i], tr2)
for i in range(1, n+1):
    print(ans - b[i] + i - 1, end=" ")

题目描述

小美拿到了一个排列，她定义$f(i)$为:将第$i$个元素取反后，形成的数组的逆序对数量。小美希望你求出$f(1)$到$f(n)$的值。排列是指一个长度为$n$的数组，1到$n$每个元素恰好出现了一次。

输入描述

第一行输入一个正整数$n$，代表排列的大小

第二行输入$n$个正整数$a_i$，代表排列的元素。

$1\le n\le 2\times 10^5$

$1\le a_i\le n$

输出描述

输出$n$个整数，第$i$个整数是$f(i)$的值。

样例

输入

3
1 2 3

输出

0 1 2

说明

第一个元素取反，数组将变成[-1,2,3]，逆序对数量为 0.
第二个元素取反，数组将变成[1,-2,3]，逆序对数量为1.
第三个元素取反，数组将变成[1,2,-3]，逆序对数量为2.