第5题-小美的排列 - Problem Detail - CodeFun2000

ID: 803

Difficulty: 9

所属公司 : 美团

时间 :2024年3月16日

题目描述

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

思路：树状数组

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

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