python

9.0 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 788. 逆序对的数量

一、题目描述

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式 第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式 输出一个整数，表示逆序对的个数。

数据范围 1≤n≤100000，数列中的元素的取值范围 [1,10^9]

输入样例：

6
2 3 4 5 6 1

输出样例：

二、前导知识

如何获取第几大+原始位置的对应关系数组?

#include <bits/stdc++.h>

using namespace std;
const int N = 500010;
int n;
int a[N], b[N];

// 输出原数组
void out() {
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts("");
}

// 功能:排序办法
// ①、数小的在前面
// ②、如果数一样大，序号小的在前
bool cmp(int x, int y) {
    if (a[x] == a[y]) return x < y;
    return a[x] < a[y];
}

// 【方法1】
void func1() {
    cin >> n;

    // ① 初始化                 ：       b[i]=a[i]
    // ② 排序(小的在前，大的在后) :        a[]
    // ③ 每个b[i]通过二分,在排序后的a[]中查找位置，记录b[i]=找到的位置
    // ④ a[]数组被重新由小到大排序
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

    // 输出原始数组
    out();

    // 原始数组由小到大排序
    // ① 由小到大排序,不用加什么greater<int>(),代码更简单
    // ② 只有由小到大排序，后面使用二分进行数值查询位置时，才能使用lower_bound二分方法
    sort(a + 1, a + n + 1);

    // 离散化，遍历原始数组b[i],找出它的排名，即b[2]=3表示第2个输入的是排名第3的
    // 这里的离散化没有用到去重，如果需要去重，参考：788_Unique.cpp
    for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + n + 1, b[i]) - a;

    // 倒序，由大到小(视业务调整)
    for (int i = n; i; i--) printf("%d ", b[i]);
}

// 【方法2】
void func2() {
    cin >> n;

    // ① 初始化                     ：b[i]=i
    // ② 排序(小的在前，大的在后)    : b[]
    // ③ a[]数组不动
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = i;

    // 输出原始数组
    out();

    // 对b[]排序
    sort(b + 1, b + n + 1, cmp);

    // 倒序，由大到小(视业务调整)
    for (int i = n; i; i--) printf("%d ", b[i]);
}

/*
  原始数组    10 8 7 9 4
  输出        1 4 2 3 5
  含义：
  （1）最大的是原始数组的a[1]=10
  （2）次大的是原始数组的a[4]=9
  （3）三大的是原始数组的a[2]=8
   ...
*/
int main() {
    // 调用方法1进行测试
    freopen("788.in", "r", stdin);
    func1();
    puts("");

    // 在第二次重定向时修改一下cin的状态
    cin.clear();
    puts("");

    // 调用方法2进行测试
    freopen("788.in", "r", stdin);
    func2();
    puts("");

    return 0;
}

为什么不喜欢使用结构体进行描述信息? 主要是因为我们想使用一种通用的办法：排序+离散化+二分 来获取对应关系数组,这时朴素的数组比较方便，带结构体的数组不太好用。

二、树状数组解法

#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
typedef long long LL;
int a[N], b[N];
int n;

int tr[N];

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

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL ans;
int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + 1 + n, b[i]) - a;

    for (int i = 1; i <= n; i++) {
        add(b[i], 1);
        ans += sum(n) - sum(b[i]);
    }
    printf("%lld", ans);
    return 0;
}

三、`d`数组的作用

数组a[]中的每个元素a[i]有三个属性：

① 数值 value
② 整体排名 rank (由大到小排序)
③ 原始位置 pos

当我们求逆序对时，只关心 ② 和 ③。 ① 在这里是一个临时的概念，它的存在导致可以求出整体的排名 ②

d[]记录的就是 ② 整体的排名 rank + ③ 原来的位置 pos

比如：d[x]=y 表示排名第x位的数，原始位置是y

Q: 排名数组d[]的构建步骤？ A:

随着a[i]读入，记录d[i] = i ,即记录输入序号，当比较数值一样时，用来判断哪个在前
实现比较函数 cmp, 如果值不一样，值大的在前；如果值一样，则输入序号大的在前
sort(d+1,d+1+n,cmp) 调用STL+自定义cmp 对d数组进行排序,最终的排序结果如下面的栗子：

输入 a[] 值 4 2 3 5 1 d[] 序号 1 2 3 4 5

结果 a[] 值 4 2 3 5 1 d[] 序号 4 1 3 2 5

可以清楚看出：

原数组没有改变
d[1]=4,表示第1名，值最大的，在a[]中第4个位置上，最大值=a[d[1]]=a[4]=5 d[2]=1,表示第2名，值次大的，在a[]中第1个位置上，次大值=a[d[2]]=a[1]=4 ....

算法步骤： 1、排名由高到低，逐个让每个数字下场,也就是 大的数字先入场，占领它在原始数组中的位置 2、当某个数字下场时，检查它左侧(也就是号比自己小的),现在已经有多少个数字存在,这此数字都符合一个特点： 数比自己大,号比自己小,也就是 逆序对的数量。

四、树状数组的作用

就是可以维护一个 动态前缀和 ,这是我起的名字，不一定准确，但事就是这么个事。普通前缀和适合于静态数组，像这样一会加进来一个，就需要计算一下前缀和，一会又加进来一个，还想算前缀和的，树状数组的优势就来了，虽然达不到O(1),但O(logN)也是很不错的运算速度了。

五、疑问

是不是可以最大排序向左看，最小排序向右看呢？需要测试一下

答案是一样可以AC！原理是一样的，从本质上说应该没有大的在前快，因为需要多计算一下sum,但实测效果两者基本一致。

六、线段树解法

// 权值线段树解法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 5e5 + 10;
int a[N], b[N];
int n;

// 线段树区间和模板
#define ls u << 1
#define rs u << 1 | 1

struct Node {
    int l, r; // 范围
    int sum;  // 区间内数字个数
} tr[N << 2]; // 4倍空间

// 创建
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
}

// 向上更新统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

// 修改点的值
void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].sum += v;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid)
        modify(ls, x, v);
    else
        modify(rs, x, v);
    pushup(u);
}

// 查询区间和
int query(int u, int l, int r) {
    if (l > r) return 0;
    if (tr[u].l == l && tr[u].r == r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    if (mid < l) return query(rs, l, r);
    if (r <= mid) return query(ls, l, r);
    return query(ls, l, mid) + query(rs, mid + 1, r);
}

LL ans;

int main() {
    cin >> n;
    // 一般使用线段树，都喜欢从下标1开始，所以我们在处理数据时尽量让下标从1开始
    // b[]在下面的代码中有两个阶段的含义，目前的含义是a[i]的备份，因为一会a[]由小到大排序后，原始数组就丢失了位置信息就不见了，需要b备份出来
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

    // ① 原始数组由小到大排序
    sort(a + 1, a + n + 1);

    // ② 离散化，遍历原始数组b[i],找出它的排名，即b[2]=3表示第2个输入的是排名第3的
    for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + n + 1, b[i]) - a;

    // 构建线段树
    build(1, 1, n); // n个数字

    // 边查边添加
    for (int i = 1; i <= n; i++) {
        modify(1, b[i], 1);           // 占据b[i]这个位置
        ans += query(1, b[i] + 1, n); // 出现的比我早，号还比我大的有多少个
    }

    // 输出
    printf("%lld\n", ans);
    return 0;
}

七、总结

树状数组讲究的是逐个下场，动态统计前缀和

9.0 KiB Raw Permalink Blame History Unescape Escape