zjh

用户名：speaksoftly

访问量：24718

签　名：

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

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

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-数的划分-题解(C++代码)蒟蒻的me也来写一写题解
浏览：948

蓝桥杯历届试题-国王的烦恼（C++代码）并查集&生成树
浏览：877

蓝桥杯历届试题-城市建设（C++代码）并查集&最小生成树kruskal
浏览：1226

你可能喜欢

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

逆序数（C++代码）正解：线段树(nlogn)单点查询区间更新

　　作者: zjh　　　　发表时间：2019-11-28 23:17:24 浏览：363　|　评论：0　

原题链接：逆序数

正解：树状数组、线段树
正常来说数据量n <= 5e5, 每个A[i] <= 1e9, 这道题数据量就太小了, (水题...没有灵魂的水题...)

以下介绍线段树应该做:
	(以下数组下标皆为1开始, 且讨论的数据量都以上面所说的正常数据量作为基准)
	
		对于当前A[i], 我们可以去获取1 ~ (i - 1) 中， 一共有多少个数大于当前A[i], 对于每一个A[i]都执行这个操作即可获得结果, 就像冒泡排序一样
		
		但这不是一个好的解题姿势, 因为时间复杂度为(n^2), 50万的平方, 必然是超时的...
		
	但现在, 有了这个思想就好处理了, 我们可以维护一个数组, 然后再挨个处理每个A[i], 比如现有这么一则数据(n = 6, A = [5, 4, 2, 6, 3, 1]), 从A[1]开始, 我们可以先获取tree数组中5前面一共有多少个已出现的数字即为当前A[i]的结果, 然后再更新tree[1 ~ 4]的所有位置+1, 表示自A[1]之后如果再出现比5小的数字, 则说明前面必然有比当前大的数字, 即为逆序对, 如A[2], 先获取, 发现tree[4] == 1, 则A[2]的逆序对结果为1, 然后更新A[1 ~ 3]... 依次类推
	
	但这样每次查找结果, 更新tree数组, 时间复杂度还是n^2, 所以我们可以根据线段树的特性进行处理, 使时间复杂度变成nlogn, 如没学过线段树, 建议先自行b站学习, 这里不过多阐述
	
	查询结果和更新基本处理结束了, 前面说过正常数据每个A[i] <= 1e9，众所周知我们的数组是开不了那么大的, 而且可以发现, n <= 5e5, 也就是说, 最坏的情况下也只会输入50万个数据, 那么剩下的1e9 - 50W剩余的空间呢??? 怎能让它就这么浪费掉了?
	
	所以引入一个概念, 叫离散化
	
		举个例子: 如果一个数据A = [1000000, 1, 6, 4], 难道我们也要开一个1000000的数组吗? 显然不太可能, 我们可以把它优化成[4, 1, 3, 2]的数据(这对结果并没有什么影响), 我们可以在输入数据的时候, 为每一个A[i]记录它的i, 表示它在输入时的位置, 以下标离散
		
		做完标记之后, 我们要进行排序, 目的是为了防止在离散的过程中出现两个或两个以上相同的数字, 而它们却很难找到对方, 并赋予相同的值, 合理的处理是让它们的值相等
		
		试想, 现有两个数据: A[1] = 10, A[2] = 5, A[3] = 10
			我们肯定不希望它离散出来的结果是Hash[1] = 2, Hash[2] = 1, 而Hash[2] = 3, 我们期望的结果是Hash[1] = 2, Hash[2] = 1, Hash[3] = 2, 这样才不会造成错误

详情请看code:
```cpp
#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 = 5e5 + 10;

// 此为快读, 优化输入速度
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;
}

int n, tree[maxn << 2], lazy[maxn << 2], Hash[maxn];	//如描述所诉
pair<int, int> A[maxn];	//pair有两个属性, first: 表示第一个数据, second: 表示第二个数据, 可以理解为一个结构体(类)里面有两个属性, 一个用来存储题目输入数据, 一个用来存储相应的位置i

// 离散时排序,  根据输入的数据进行升序
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

// 懒标记, 加速线段树
void push_down(int node, int start, int end) {
    lazy[node << 1] += lazy[node];
    lazy[node << 1 | 1] += lazy[node];
    int mid = (start + end) >> 1;
    tree[node << 1] += (mid - start + 1) * lazy[node];
    tree[node << 1 | 1] += (end - mid) * lazy[node];
    lazy[node] = 0;
}

// 更新1～Hash[i] - 1
void update(int node, int start, int end, int l, int r) {
    if (l > r) return ;
    if (l <= start && r >= end) {
        lazy[node]++;
        tree[node] += end - start + 1;
        return ;
    }
    if (lazy[node]) push_down(node, start, end);
    int mid = (start + end) >> 1;
    if (l <= mid) update(node << 1, start, mid, l, r);
    if (r > mid) update(node << 1 | 1, mid + 1, end, l, r);
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

// 获取tree[ Hash[i] ]的前面有多少个大于它的数字
int query(int node, int start, int end, int lr) {
    if (start == end) return tree[node];
    if (lazy[node]) push_down(node, start, end);
    int mid = (start + end) >> 1;
    int ans = 0;
    if (lr <= mid) ans += query(node << 1, start, mid, lr);
    else ans += query(node << 1 | 1, mid + 1, end, lr);
    return ans;
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) A[i].first = read(), A[i].second = i;
    sort(A + 1, A + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
		// A[0] 不存在, 所以特判 i != 1, 如果当前A[i] == A[i - 1], 则让 Hash[ A[i] 原来的位置 ] = 上一个离散出来的值
        if (i != 1 && A[i].first == A[i - 1].first) Hash[A[i].second] = Hash[A[i - 1].second];
        else Hash[A[i].second] = i;	// 否则跟着当前 i 走即可
    }
    ll res = 0;	//某谷原题会爆int, 所以特用long long
    for (int i = 1; i <= n; ++i) {
        res += query(1, 1, n, Hash[i]);	//先获取当前Hash[i]前面有多少个大于它的数字
        update(1, 1, n, 1, Hash[i] - 1);	//再更新1 ~ Hash[i] - 1 的每个位置+1
    }
    cout << res << endl;
    return 0;
}
```

0.0分

6 人评分

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

zjh

TA的其他文章

你可能喜欢

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

C语言训练-求车速（C语言代码）

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

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

C语言考试练习题_排列（C++代码）

逆序数（C++代码）正解：线段树(nlogn)单点查询区间更新

评论区

精彩推荐

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

【明明的随机数】（C语言代码）

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

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

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

图形输出（C语言代码）

C二级辅导-分段函数（C语言代码）

程序员的表白（C语言代码）

神奇的fans （C语言代码）

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

zjh

TA的其他文章

你可能喜欢

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

C语言训练-求车速 （C语言代码）

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

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

C语言考试练习题_排列 （C++代码）

逆序数 （C++代码）正解：线段树(nlogn)单点查询区间更新

评论区

精彩推荐

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

【明明的随机数】 （C语言代码）

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

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

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

图形输出 （C语言代码）

C二级辅导-分段函数 （C语言代码）

程序员的表白 （C语言代码）

神奇的fans （C语言代码）

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

C语言训练-求车速（C语言代码）

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

C语言考试练习题_排列（C++代码）

逆序数（C++代码）正解：线段树(nlogn)单点查询区间更新

　　评论区

【明明的随机数】（C语言代码）

图形输出（C语言代码）

C二级辅导-分段函数（C语言代码）

程序员的表白（C语言代码）