一个人的巴黎

用户名：uq_36478041918

访问量：15003

签　名：

等　　级
排　　名	105
经　　验	8305
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

斐波那契(快速矩阵幂运算)
浏览：359

01背包问题(动态规划自下而上递推)
浏览：481

简单型背包(DFS深搜)
浏览：135

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

蓝桥杯历届试题-小朋友排队【树状数组 C++ 详解】

　　作者: 一个人的巴黎　　　　发表时间：2022-02-23 15:56:17 浏览：996　|　评论：0　

原题链接：蓝桥杯历届试题-小朋友排队

**题目分析**：

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

例如：样例输入 (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 个元素的和。
![在这里插入图片描述](https://img-blog.csdnimg.cn/4f58456b9c8c4df182707d6282d009b5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQOS4gOS4quS6uueahOW3tOm7jg==,size_10,color_FFFFFF,t_70,g_se,x_16#pic_center)
设数组 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~6~ 表示sum(4,6]
从而有了一个lowbit函数：
```cpp
void lowbit(int n){
    return n-(n&(n-1));
}
```
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~6~ 变动时，假设增加v，index+lowbit(index)=6+lowbit(6)=8，c~8~ 也要变动，增加v
从c~k~ 的含义理解：c~6~ 表示区间[4,6]的和，c~6~ 改变了，必然会影响后面区间的和

从而有了一个update函数：

```cpp
//原数组的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;
}
```

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

```cpp
int getsum(int c[],int i){
    int sum=0;
    for(int k=i;k>=1;k-=lowbit(k))
        sum+=c[k];
    return sum;
}
```
现在编写一个树状数组求区间和的模板：

```cpp
#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
}
```
**==懂得树状数组的可以直接看下面的代码，已注解：==**
```cpp
#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;

}
```

0.0分

11 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

1065

DNA （C++代码）

C语言训练-大、小写问题（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

上车人数（C语言代码）

蓝桥杯历届试题-小朋友排队【树状数组 C++ 详解】

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

妹子杀手的故事（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

完数（C语言代码）

1017题解

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

模拟计算器（C++代码）

字符逆序（C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

1065

DNA （C++代码）

C语言训练-大、小写问题 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

上车人数 （C语言代码）

蓝桥杯历届试题-小朋友排队【树状数组 C++ 详解】

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

妹子杀手的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

完数 （C语言代码）

1017题解

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

模拟计算器 （C++代码）

字符逆序 （C语言代码）

C语言训练-大、小写问题（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

上车人数（C语言代码）

　　评论区

妹子杀手的故事（C语言代码）

完数（C语言代码）

模拟计算器（C++代码）

字符逆序（C语言代码）