思路[贪心]：若某个小朋友构成k对逆序对，则这个个小朋友至少交换k次。

暴力

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int h[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &h[i]);

    LL ans = 0;

    // 遍历n个小朋友
    for(int i = 0; i < n; i++)
    {
        int res = 0;    // i构成多少个逆序对
        // 找i前面大于它的人数
        for(int j = 0; j < i; j++)
            if(h[j] > h[i])
                res++;

        // 找i后面小于它的个数
        for(int j = i + 1; j < n; j++)
            if(h[j] < h[i])
                res++;


        ans += res * (res + 1) / 2;        
    }

    cout << ans << endl;

    return 0;
}

使用树状数组优化

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
int h[N];
int t[N], cnt[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for(; x <= N; x += lowbit(x)) t[x] += c;
}

int sum(int x)
{
    int res = 0;
    for(; x; x -= lowbit(x)) res += t[x];
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]); 

    // 每个数前面有多少个比它大
    for(int i = 1; i <= n; i++)
    {
        cnt[i] += sum(N - 1) - sum(h[i]);
        add(h[i], 1);
    }

    memset(t, 0, sizeof t);
    // 每个数后面有多少个比它小
    for(int i = n; i >= 1; i--)
    {
        cnt[i] += sum(h[i] - 1);
        add(h[i], 1);
    }

    LL ans = 0;
    for(int i = 1; i <= n; i++) ans += cnt[i] * (LL)(cnt[i] + 1) / 2;

    cout << ans << endl;

    return 0;
}

使用线段树优化

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
int h[N];
int cnt[N];

struct Node
{
    int l, r, sum;
} t[N * 4];

void pushup(int p)
{
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}

void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if(l == r) return;
    int mid = l + r >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

// 查询区间和
int query(int p, int l, int r)
{
    if (t[p].l >= l && t[p].r <= r) return t[p].sum; // 所查询区间完全包含该区间
    int mid = t[p].l + t[p].r >> 1;
    int sum = 0;
    if (l <= mid) sum += query(p << 1, l, r);
    if (r >= mid + 1) sum += query(p << 1 | 1, l, r);
    return sum;
}


void change(int p, int x, int v)
{
    if (t[p].l == t[p].r) t[p].sum += v;
    else
    {
        int mid = t[p].l + t[p].r >> 1;
        if (x <= mid) change(p << 1, x, v);
        else change(p << 1 | 1, x, v);
        pushup(p);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]); 


    build(1, 1, N - 1); // 建树

    int res = 0;
    // 每个数前面有多少个比它大
    for (int i = 1; i <= n; i++)
    {
        cnt[i] += query(1, h[i] + 1, N - 1);
        change(1, h[i], 1); // 大小为h[i]的数加一
    }

    // 每个数后面有多少个比它小
    for(int i = 0; i < N * 4; i++) t[i].sum = 0;
    for (int i = n; i >= 1; i--)
    {
        cnt[i] += query(1, 0, h[i] - 1);
        change(1, h[i], 1); // 大小为h[i]的数加一
    }

    LL ans = 0;
    for (int i = 1; i <= n; i++) ans += cnt[i] * (LL)(cnt[i] + 1) / 2;

    cout << ans << endl;

    return 0;
}