solution.md

# 小朋友排队


**题目描述**

n 个小朋友站成一排。

现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。

开始的时候，所有小朋友的不高兴程度都是 0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 3），依次类推。当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。


**输入格式**

输入的第一行包含一个整数 n，表示小朋友的个数。

第二行包含 n 个整数 H1,H2,…,Hn，分别表示每个小朋友的身高。


**输出格式**

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。


**数据范围**

```
1≤n≤100000,
0≤Hi≤1000000
```

**输入样例：**

```
3
3 2 1
```

**输出样例：**

```
9
```

**样例解释**

首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

以下<span style="color:red">错误</span>的一项是？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
#define ll long long
using namespace std;
int const MAX = 1e5 + 5;
ll cnt[MAX], ans;
int n;

struct DATA
{
    int idx;
    ll num;
} d[MAX];

bool cmp(DATA a, DATA b)
{
    return a.num < b.num;
}

void Solve(int l, int mid, int r)
{
    int i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (d[i].num <= d[j].num)
            i++;
        else
        {
            cnt[d[j].idx] += (ll)(mid - i + 1);

            j++;
        }
    }
    i = mid, j = r;
    while (i >= l && j >= mid + 1)
    {
        if (d[i].num > d[j].num)
        {
            cnt[d[i].idx] += (ll)(j - mid);
            i--;
        }
        else
            j--;
    }
    sort(d + l, d + r + 1, cmp);

    return;
}

void Div(int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
    Div(l, mid);
    Div(mid + 1, r);
    Solve(l, mid, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &d[i].num);
        d[i].idx = i;
    }
    ans = 0;
    Div(0, n - 1);
    for (int i = 0; i < n; i++)
        ans += cnt[i] * cnt[i] / 2;
    printf("%lld\n", ans);
}
```

## 选项

### A

```c
typedef long long LL;
const int N = 1e6 + 10;
int h[N], s[N], tr[N];
int n;

int lowbit(int x) { return x & -x; }
int add(int x)
{
    for (int i = x; i < N; i += lowbit(i))
        tr[i]++;
}
int q(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i], h[i]++;

        s[i] = q(N - 1) - q(h[i]);
        add(h[i]);
    }

    memset(tr, 0, sizeof tr);

    for (int i = n - 1; i >= 0; i--)
        s[i] += q(h[i] - 1), add(h[i]);

    LL res = 0;
    for (int i = 0; i < n; i++)
        res += (LL)s[i] * (s[i] + 1) / 2;
    cout << res;

    return 0;
}
```

### B

```c
struct childInfo
{
    int location;
    int valueNum;
};

int cnt[100005];

void Merge_sort1(vector<childInfo> &tempChild, int left, int right)
{
    if (left >= right - 1)
        return;
    int mid = (left + right) / 2;
    Merge_sort1(tempChild, left, mid);
    Merge_sort1(tempChild, mid, right);
    int i = left, j = mid, t = 0;
    childInfo *temp = new childInfo[right - left];
    while (i < mid || j < right)
    {
        if (j >= right || i < mid && tempChild[i].valueNum <= tempChild[j].valueNum)
            temp[t++] = tempChild[i++];
        else
        {
            cnt[tempChild[j].location] += mid - i;
            temp[t++] = tempChild[j++];
        }
    }
    t = 0;
    for (int k = left; k < right; k++)
        tempChild[k] = temp[t++];
    delete[] temp;
}

void Merge_sort2(vector<childInfo> &tempChild, int left, int right)
{
    if (left >= right - 1)
        return;
    int mid = (left + right) / 2;
    Merge_sort2(tempChild, left, mid);
    Merge_sort2(tempChild, mid, right);
    childInfo *temp = new childInfo[right - left];
    int i = mid - 1, j = right - 1, t = right - left - 1;
    while (i >= left || j >= mid)
    {
        if (i < left || j >= mid && tempChild[i].valueNum <= tempChild[j].valueNum)
            temp[t--] = tempChild[j--];
        else
        {
            cnt[tempChild[i].location] += j - mid + 1;
            temp[t--] = tempChild[i--];
        }
    }
    t = 0;
    for (int i = left; i < right; i++)
        tempChild[i] = temp[t++];
    delete[] temp;
}
int main()
{
    int n;
    cin >> n;
    vector<childInfo> childLists;
    for (int i = 0; i < n; i++)
    {
        childInfo tempChild;
        tempChild.location = i;
        cin >> tempChild.valueNum;
        childLists.push_back(tempChild);
    }
    vector<childInfo> childLists1(childLists.begin(), childLists.end());
    Merge_sort1(childLists, 0, childLists.size());
    Merge_sort2(childLists1, 0, childLists1.size());
    long long sum = 0;
    for (int i = 0; i < childLists.size(); i++)
        sum += 1ll * (1 + cnt[i]) * cnt[i] / 2;
    cout << sum;
    return 0;
}
```

### C

```c
struct childInfo
{
    int location;
    int valueNum;
};

bool lowCompare(childInfo temp1, childInfo temp2)
{
    return temp1.valueNum > temp2.valueNum;
}

bool upCompare(childInfo temp1, childInfo temp2)
{
    return temp1.valueNum < temp2.valueNum;
}

int main()
{
    int childNums;
    cin >> childNums;
    vector<childInfo> childLists;
    vector<childInfo> childLists1;
    vector<childInfo> childLists2;
    for (int i = 0; i < childNums; i++)
    {
        childInfo tempInfo;
        tempInfo.location = i;
        scanf("%d", &tempInfo.valueNum);
        childLists.push_back(tempInfo);
        childLists1.push_back(tempInfo);
        childLists2.push_back(tempInfo);
    }
    sort(childLists1.begin(), childLists1.end(), lowCompare);
    sort(childLists2.begin(), childLists2.end(), upCompare);

    long long int count = 0;
    for (int m = 0; m < childNums; m++)
    {
        int sadNum = 0;
        long long int count1 = 0, count2 = 0;
        int compareNum = childLists[m].valueNum, compareLoc = childLists[m].location;

        for (int n = 0; n < childNums; n++)
        {
            if (compareNum < childLists1[n].valueNum)
            {
                if (compareLoc > childLists1[n].location)
                {
                    sadNum++;
                    count1 += sadNum;
                }
            }
            else
            {
                break;
            }
        }

        for (int n = 0; n < childNums; n++)
        {
            if (compareNum > childLists2[n].valueNum)
            {
                if (compareLoc < childLists2[n].location)
                {
                    sadNum++;
                    count2 += sadNum;
                }
            }
            else
            {
                break;
            }
        }
        count += count1 + count2;
    }
    cout << count << endl;
    return 0;
}
```