求逆序数 【模板】

逆序数

https://ac.nowcoder.com/acm/problem/15163

归并排序做法

什么是归并排序呢?用一张图来说明:

图片说明
(本图引用自浙江大学数据结构MOOC

归并排序可以理解为:将两个有序的序列合并成一个有序的序列。
我们递归地执行,直到区间分割到单个元素,然后再递归回去,去执行有序序列的合并,就完成了归并排序。

当出现a[x] > a[y]的情况时,出现逆序

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &x)
const int N = 1e5 + 7;
typedef long long ll;
int n, a[N], b[N];
ll ans;
void mergeSort(int L, int R) {
    if (L == R) return;
    int mid = (L + R) >> 1;
    mergeSort(L, mid);
    mergeSort(mid + 1, R);
    // 此时两个区间内已经有序
    int x = L, y = mid + 1;  // 指向两个有序子列的下标
    for (int i = 1; i <= R - L + 1; ++i) {
        if (x <= mid && y <= R) {  // 两个有序子列合并成一个有序列
            if (a[x] > a[y]) {
                ans += mid - x + 1;  // 统计答案
                // 注意这里用mid来减而非它正确的位置
                b[i] = a[y++];
            } else
                b[i] = a[x++];
        } else {
            if (x <= mid) b[i] = a[x++];
            if (y <= R) b[i] = a[y++];
        }
    }
    for (int i = R - L + 1; i; --i) a[R--] = b[i];  // 覆盖回去
}
int main() {
    sc(n);
    for (int i = 1; i <= n; i++) sc(a[i]);
    mergeSort(1, n);
    printf("%lld\n", ans);
    return 0;
}

树状数组做法

考虑维护一个树状数组。
在每插入一个值之前,查询此时有多少个比它大的值。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
#define lowbit(x) ((x) & (-x))
int tree[N];
inline void upd(int i) {
    while (i < N) {
        ++tree[i];
        i += lowbit(i);
    }
}
inline ll query(int i) {
    ll ans = 0;
    while (i) {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}
inline ll query(int a, int b) { return query(b) - query(a - 1); }
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll n, x, ans = 0;
    cin >> n;
    rep(i, 1, n) {
        cin >> x;
        ans += query(x + 1, N - 1);
        upd(x);
    }
    cout << ans << '\n';
    return 0;
}

线段树做法

线段树做法和BIT是一个道理

// https://blog.nowcoder.net/n/fd7f7193086c4a4b97e0dee0b031ac38
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int W[N << 2];
inline void insert(int now, int l, int r, int x) {
    ++W[now];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid)
        insert(now << 1, l, mid, x);
    else
        insert(now << 1 | 1, mid + 1, r, x);
}
inline int find(int now, int l, int r, int lc, int rc) {
    if (lc <= l && r <= rc) return W[now];
    int mid = (l + r) >> 1, res = 0;
    if (lc <= mid) res += find(now << 1, l, mid, lc, rc);
    if (rc > mid) res += find(now << 1 | 1, mid + 1, r, lc, rc);
    return res;
}
int main() {
    int n;
    long long res = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        ++x;
        if (x != N) res += find(1, 1, N, x + 1, N);
        insert(1, 1, N, x);
    }
    printf("%lld", res);
    return 0;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

点赞 评论 收藏
分享
07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务