题目描述

样例

输入

6
5 4 2 6 3 1

输出

11

算法1

(树状数组) $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int cnt[N], tr[N];
int n;
struct innt {
    int idx;
    int num;
}a[N];
bool cmp(innt a, innt b)
{
    if (a.num == b.num)return a.idx < b.idx;
    return a.num < b.num;
}
int lowbit(int x)
{
    return -x & x;
}
void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))tr[i] += c;
}
int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))res += tr[i];
    return res;
}
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++)cin >> a[i].num, a[i].idx = i;
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)cnt[a[i].idx] = i;
    //离散化使得数据从从第一个开始的数分布在树状数组中
    for (int i = 1; i <= n; i++)
    {
        add(cnt[i], 1);
        ans += i - query(cnt[i]);
        /*他是第i大的数，前面有query（i）个数比他小，那么后面就还有i-query(i)个数比他小，
        从而构成i-query(i)逆序对*/
    }
    cout << ans << endl;
    return 0;
}