【洛谷 P2513】 [HAOI2009]逆序对数列（DP）

这道题目还可以使用树状数组或线段树来实现，时间复杂度也为 $\mathcal{O}(n\log n)$。这里给出使用树状数组的实现代码。

解题思路：

1. 读入数据；
2. 将原数列离散化，得到一个新的数列 b；
3. 从右往左依次将 b 数列中的元素插入到树状数组中，并计算逆序对数；
4. 输出逆序对数。

代码实现：

#include <cstdio>
#include <cstdlib>
#include <algorithm>

const int MAXN = 500005;

struct Node {
    int val, id;
    bool operator<(const Node& other) const {
        return val < other.val;
    }
} nodes[MAXN];

int n, a[MAXN], b[MAXN], c[MAXN];
long long ans;
inline int lowbit(int x) { return x & (-x); }

void update(int x, int val)
{
    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += val;
    }
}

int query(int x)
{
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        nodes[i] = {a[i], i};
    }
    std::sort(nodes + 1, nodes + n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == 1 || nodes[i].val != nodes[i - 1].val) {
            ++cnt;
        }
        b[nodes[i].id] = cnt;
    }
    for (int i = n; i >= 1; --i) {
        ans += query(b[i] - 1);
        update(b[i], 1);
    }
    printf("%lld\n", ans);
    return 0;
}

注意事项：

- 在对原数列进行离散化时，需要记录每个元素在原数列中的位置，便于后面计算逆序对数；
- 设树状数组的大小为 $n$，则树状数组中的下标从 $1$ 到 $n$，而不是从 $0$ 到 $n-1$；
- 在计算逆序对数时，需要查询离散化后的数列中比当前元素小的元素个数，即查询 $b_i-1$ 位置上的值；
- 在插入元素时，需要将离散化后的数列的元素从右往左依次插入树状数组中，而不是从左往右。