怀旧书本
文章目录

树状数组

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e5 + 5;
LL sa[MAX];
int idx[MAX];
LL nums[MAX], nnums[MAX];
LL query(int idx) {
    LL ans = 0;
    for (int i = idx; i; i -= (i & -i)) {
        ans += sa[i];
    }
    return ans;
}
void update(int idx, int d) {
    for (int i = idx; i <= MAX; i +=(i & -i)) {
        sa[i] += d;
    }
}
bool cmp(int a, int b) {
    return nums[a] < nums[b];
}
int main() {
    memset(sa, 0, sizeof sa);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i )  {
       cin >> nums[i];
       idx[i] = i;
    }
    sort(idx, idx + n, cmp);
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            nnums[idx[i]] = 1;
        } else {
            nnums[idx[i]] = nnums[idx[i - 1]] + ((nums[idx[i]] == nums[idx[i - 1]]) ? 0 : 1);
        }
    }

    LL ans = 0;
    for (int i = n; i >= 1; --i) {
        ans += query(nnums[i - 1] - 1);
        update(nnums[i - 1], 1);
    }
    cout << ans << endl;
    return 0;
}

归并排序

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MAX = 1e5 + 5;
LL nums[MAX], tmp[MAX];

LL merge_sort(LL nums[], int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL lc = merge_sort(nums, l, mid);
    LL rc = merge_sort(nums, mid + 1, r);
    LL result = lc + rc;
    LL i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
            result += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (LL i = l; i <= r; ++i) nums[i] = tmp[i - l];
    return result;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> nums[i];
    cout <<  merge_sort(nums, 0, n - 1) << endl;
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/reverse-pair-binary-indexed-tree-merge-sort/
最后修改日期:2020年4月26日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。