蓝桥杯2014年省赛真题-小朋友排队【树状数组】_n个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置

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

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

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

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

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

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

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

数据规模和约定
对于100%的数据，1< =n< =100000，0< =Hi< =1000000。

输出
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
样例输入
3
3 2 1
样例输出
9
-----------------------------------------------------------------------------

题目分析：
表面上看，这是一道排序题，但实际上，这道题目不仅仅要求简单的排序，因为题目要求的是小朋友从低到高排序后，他们的不高兴程度之和的最小值，也就是求逆序对数的题目。

例如：样例输入 (3, 2, 1) 中，有 3 个逆序对—— (3, 2) , (3, 1) , (2, 1) ，使用使小朋友不高兴之和最小的排序方法后，即首先交换身高为 3 和 2 的小朋友，再交换身高为 3 和 1的小朋友，再交换身高为 2 和 1 的小朋友，每一个逆序对的两个元素都被要求交换了一次，而与 3 有关的逆序对为 (3, 2) 和 (3, 1) ，与 2 有关的逆序对为 (3, 2) 和 (2, 1) ，与 1 有关的逆序对为 (3, 1) 和 (2, 1) ，显然可以看出每个小朋友都被要求交换的两次。

综上所述，题目的关键是求出小朋友的身高在所有逆序对中出现的次数，也就是包含这个元素的逆序对的个数，更直接的说法是对每一个元素，求出在它前面大于它的元素的个数和在它后面小于它的元素的个数之和。最后计算出每个元素的不高兴程度并相加即可。

为了求小朋友的身高在所有逆序对中出现的次数，我们很容易想到使用暴力法解决，但是，看清楚数据规模和约定：对于 100% 的数据，1<=n<=100000，0<=Hi<=1000000，这种方法肯定会超出时间限制：1.0s ，所以我们要采用另一种数据结构——树状数组来解决这道题。
　　
要求区间和有两种方法：
1.前缀和数组(静态数据):维护一个b数组存储前i项和即可
但是当原数组a[] 的一个数变动时，b数组后面所有的数都要变动，时间复杂度为O(n),而用树状数组可以加快为O(logn)
2.树状数组 c (对于算法竞赛，数学推导略，记住就行)
树状数组的特点是快速地求前 n 个元素的和。

设数组 A[n] , n=1 , 2 , 3 … ，树 C ，令这棵树的结点编号为 C1 , C2 , … Cn ，每个结点的值为这棵树的值的总和，则：
　　C1 = A[1]
　　C2 = A[1] + A[2]
　　C3 = A[3]
　　C4 = A[1] + A[2] + A[3] + A[4]
　　C5 = A[5]
　　C6 = A[5] + A[6]
　　C7 = A[7]
　　C8 = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]

c_k 的含义是某个区间的和：[k-lowbit(k),k]
（Ci = A(n-2^k+1) + … + Ai）
lowbit(k)是k的二进制最后一个1代表的数
如：lowbit(6)=lowbit(110)=2
所以c₆ 表示sum(4,6]
从而有了一个lowbit函数：

void lowbit(int n){
    return n-(n&(n-1));
}
1
2
3

n-(n&(n-1))的含义：
举例：n=10, n-1=9
10的二进制1010,
9的二进制1001,
1010&1001=1000;
1010-1000=10,
转化为十进制为2，即10的二进制1010最后一个1代表的数

由c_k 的含义引出一个性质：当位置index的数变动时，位置index+lowbit(index)的值也跟着变动
如：index=6时，c₆ 变动时，假设增加v，index+lowbit(index)=6+lowbit(6)=8，c₈ 也要变动，增加v
从c_k 的含义理解：c₆ 表示区间[4,6]的和，c₆ 改变了，必然会影响后面区间的和

从而有了一个update函数：

//原数组的i位置，增加v后，更新c数组，n为边界
void update(int n,int i,int v,int c[]){
    for(int k=i;k<=n;k+=lowbit(k))
        c[k]+=v;
}
1
2
3
4
5

要求区间和，只要求两个前缀和相减即可，引出前缀和的求解函数getsum

int getsum(int c[],int i){
    int sum=0;
    for(int k=i;k>=1;k-=lowbit(k))
        sum+=c[k];
    return sum;
}
1
2
3
4
5
6

现在编写一个树状数组求区间和的模板：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int lowbit(int n) {
    return n - (n & (n - 1));
}

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

int getsum(int c[], int i) {
    int sum = 0;
    for (int k = i; k >= 1; k -= lowbit(k))
        sum += c[k];
    return sum;
}

int main() {
    int arr[] = { 1,2,3,4,5,6,7,8 };
    int c[9];//c[]从c[1]开始计数
    memset(c, 0, sizeof(c));
    for (int i = 0; i < 8; i++) {//扫描arr[],更新c[]
        update(9, i + 1, arr[i], c);
    }
    cout << getsum(c, 5) << endl;//求arr[]前5项的和:15
    cout << getsum(c, 7) - getsum(c, 4) << endl;//求第5项至第7项的和:18
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

懂得树状数组的可以直接看下面的代码，已注解：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int h[100000];
long long cnt[100000];//记录每个孩子的交换次数
int c[1000001];//身高转变为其数组下标！！！

int lowbit(int n) {
    return n - (n & (n - 1));
}

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

int getsum(int c[], int i) {
    int sum = 0;
    for (int k = i; k >= 1; k -= lowbit(k))
        sum += c[k];
    return sum;
}

int main() {
    int n;
    cin >> n;
    int MaxH = -1;
    for (int i = 0; i < n; i++){
        cin >> h[i];
        if (h[i] > MaxH)  MaxH = h[i];//最大身高
    }
    
    for (int i = 0; i < n; i++) {
        update(MaxH + 1, h[i] + 1, 1, c);//在相应位置计数变为1，用树状数组维护某个区间内数据出现的个数
        int sum = getsum(c, h[i] + 1);//小于等于h[i]+1的数据出现的个数
        cnt[i] += (i + 1) - sum;//得到当前数据左侧比数据大的数的个数
    }

    memset(c, 0, sizeof(c));//c[]清零,从后往前更新
    for (int i = n-1; i >= 0; i--) {
        update(MaxH + 1, h[i] + 1, 1, c);//在相应位置计数变为1，用树状数组维护某个区间内数据出现的个数
        cnt[i] += getsum(c, h[i]);//小于h[i]+1的数据出现的个数
    }
    
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (cnt[i] * (cnt[i] + 1) / 2);
    }
    cout << ans << endl;
    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54