zjh

用户名：speaksoftly

访问量：22936

签　名：

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

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

　　自我简介：

TA的其他文章

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1346

你可能喜欢

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

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

　　作者: zjh　　　　发表时间：2019-08-25 00:11:43 浏览：1697　|　评论：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编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

tym777

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

2021-12-10 13:36:53

zjh

TA的其他文章

你可能喜欢

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

点我有惊喜！你懂得！

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

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

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

评论区

精彩推荐

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

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

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

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

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

大家好，我是验题君

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

C语言程序设计教程（第三版）课后习题10.7 （用指针求解）

上车人数（C语言代码）

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

zjh

TA的其他文章

你可能喜欢

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

点我有惊喜！你懂得！

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

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

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

评论区

精彩推荐

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

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

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

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

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

大家好，我是验题君

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

C语言程序设计教程（第三版）课后习题10.7 （用指针求解）

上车人数 （C语言代码）

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

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

　　评论区

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

上车人数（C语言代码）