zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-k倍区间（C++代码）前缀和O(n)算法
浏览：863

蓝桥杯历届试题-小朋友排队（C++代码）线段树O(nlogm)算法
浏览：735

蓝桥杯历届试题-小朋友排队（C++代码）树状数组O(nlogm)算法
浏览：1758

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

蓝桥杯历届试题-小朋友排队（C++代码）树状数组O(nlogm)算法

　　作者: zjh　　　　发表时间：2019-08-25 00:11:43 浏览：1758　|　评论：1　

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

```cpp
双倍经验：https://www.lintcode.com/problem/count-of-smaller-number-before-itself/description?_from=ladder&&fromId=26
建议先把这道题做完之后再来做此题；

思路：相信看到题目的你第一时间想到的应该是冒泡排序，但是如果冒泡排序的话n <= 1e5 时间复杂度是O(n^2)，这必然会TLE，并且冒泡排序并不能保证移动次数最小。
    我们知道最终从低到高排列，而交换的都是不满足前小后大这一规律，所以我们很容易想到逆序对（i < j && A[i] > A[j])。
    如果能想到逆序对，那么就已经做对一半了。
    小朋友最小交换次数就是该小朋友在（正反逆序对（反：它前面有多少个数大于它； 正：它后面有多少个数小于它））中出现的次数总和，而交换 k 次不高兴程度就增加 k，所以最后每个小朋友的不高兴程度就是 1 ～ k 的累加和。这样只要能统计处该小朋友在所有逆序对
    比如样例（3， 2， 1）
    反逆序对：0，1，2
    正逆序对：2，1，0
    总      和：2，2，2
    最终对每个小朋友的k进行单独的1～k累加就是答案：9
	最后利用高斯算法求每个小朋友逆序对个数的累加和
#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "map"
#include "vector"
#include "stack"
#include "set"
#include "climits"

using namespace std;

typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1000010;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

//tree：结点数组，A：每个小朋友的身高，B：逆序对总数
int tree[maxn], A[maxn], B[maxn], n;

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

void update(int x, int val) {
    while(x < maxn) {
        tree[x] += val;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    n = read();
    for(int i = 0; i < n; ++i) {
        A[i] = read() + 1;
        B[i] = query(A[i]);		//求当前小朋友前面有多少个比自己高的小朋友
        //区间更新，根据差分update(L, val), update(R + 1, -val)
		//得到L = 1, R = A[i]，这里的R本来要 + 1，但是因为我们要更新的是1-A[i] - 1的区间，所以这里R = A[i] - 1 + 1 = A[i]
		update(1, 1);
        update(A[i], -1);
    }
    memset(tree, 0, sizeof tree);	//初始化用过一次的tree
    for(int i = n - 1; i >= 0; --i) {
        B[i] += query(A[i]);	//求当前小朋友后面有多少个比自己矮的小朋友
        update(A[i] + 1, 1);	//这里就不需要R了，只需要L = A[i] + 1即可，不明白的话自己手动模拟一遍就知道了
    }
    ll res = 0;
    for(int i = 0; i < n; ++i) res += (ll)(B[i] + 1) * B[i] / 2;	//高斯算法求 1～B[i] 的累加和
    printf("%lld\n", res);
    return 0;
}
```

0.0分

8 人评分

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

　　评论区

tym777

int lowbit(int x) {
    return x & -x;
}
这段的作用是什么啊？

2021-12-10 13:36:53

zjh

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

【出圈】（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

C二级辅导-温度转换（C++代码）

蓝桥杯历届试题-小朋友排队（C++代码）树状数组O(nlogm)算法

评论区

精彩推荐

计算质因子（C++代码）100以内质数直接打表就好了

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

点我有惊喜！你懂得！

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

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

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

用筛法求之N内的素数。（C语言代码）

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

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

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

zjh

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

【出圈】 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

C二级辅导-温度转换 （C++代码）

蓝桥杯历届试题-小朋友排队 （C++代码）树状数组O(nlogm)算法

评论区

精彩推荐

计算质因子 （C++代码）100以内质数直接打表就好了

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

点我有惊喜！你懂得！

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

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

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

用筛法求之N内的素数。 （C语言代码）

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

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

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

【出圈】（C语言代码）

C二级辅导-温度转换（C++代码）

蓝桥杯历届试题-小朋友排队（C++代码）树状数组O(nlogm)算法

　　评论区

计算质因子（C++代码）100以内质数直接打表就好了

用筛法求之N内的素数。（C语言代码）