信息学奥赛一本通T1311-求逆序对（从52到100的艰苦历程）

参考代码:

使用的是归并排序

52分的代码：

#include

#include

#include

using namespace std;

long long merge(vector

    int i = start;

    int j = mid + 1;

    int k = start;

    long long count = 0;

    while (i <= mid && j <= end) {

        if (arr[i] <= arr[j]) {

            temp[k++] = arr[i++];

        } else {

            temp[k++] = arr[j++];

            count += mid - i + 1;

        }

    }

    while (i <= mid) {

        temp[k++] = arr[i++];

    }

    while (j <= end) {

        temp[k++] = arr[j++];

    }

    for (int l = start; l <= end; l++) {

        arr[l] = temp[l];

    }

    return count;

}

long long mergeSort(vector

    if (start >= end) {

        return 0;

    }

    int mid = start + (end - start) / 2;

    long long count = 0;

    count += mergeSort(arr, temp, start, mid);

    count += mergeSort(arr, temp, mid + 1, end);

    count += merge(arr, temp, start, mid, end);

    return count;

}

int main() {

    int n;

    cin >> n;

    vector

    for (int i = 0; i < n; i++) {

        cin >> arr[i];

    }

    vector

    long long inversionCount = mergeSort(arr, temp, 0, n - 1);

    cout << inversionCount << endl;

    return 0;

}

我以为可以在归并排序的基础上进行优化一下就可以过了，然后就是62分，76分

然后看了一下题解，说要用BIT（树状数组）进行解题才不会时间超限

第一次的BIT（树状数组）就是90分，然后优化一下才过了

第一次的BIT，90分的参考代码：

#include

#include

#include

using namespace std;

// 树状数组类

class BIT {

public:

    BIT(int size) : bit(size + 1, 0) {}

    // 更新指定位置的计数

    void update(int index, int delta) {

        while (index < bit.size()) {

            bit[index] += delta;

            index += lowbit(index);

        }

    }

    // 获取指定位置的前缀和

    int query(int index) {

        int sum = 0;

        while (index > 0) {

            sum += bit[index];

            index -= lowbit(index);

        }

        return sum;

    }

private:

    vector

    // 计算最低位的1的位置

    int lowbit(int x) {

        return x & (-x);

    }

};

int main() {

    int n;

    cin >> n;

    vector

    for (int i = 0; i < n; i++) {

        cin >> arr[i];

    }

    // 离散化，通过排序得到每个元素在排序后的序列中的位置

    vector

    sort(sortedArr.begin(), sortedArr.end());

    for (int i = 0; i < n; i++) {

        arr[i] = lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin() + 1;

    }

    // 创建树状数组

    BIT bit(n);

    long long count = 0;

    // 从右往左遍历离散化后的数组

    for (int i = n - 1; i >= 0; i--) {

        count += bit.query(arr[i] - 1);  // 获取比当前元素小的元素的计数

        bit.update(arr[i], 1);  // 当前元素出现一次，更新计数

    }

    cout << count << endl;

    return 0;

}

最后的AC代码：(多提交几次就过了)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// 树状数组类

class BIT {

public:

    BIT(int size) : bit(size + 1, 0) {}

    // 更新指定位置的计数

    void update(int index, int delta) {

        while (index < bit.size()) {

            bit[index] += delta;

            index += lowbit(index);

        }

    }

    // 获取指定位置的前缀和

    int query(int index) {

        int sum = 0;

        while (index > 0) {

            sum += bit[index];

            index -= lowbit(index);

        }

        return sum;

    }

private:

    vector<int> bit;

    // 计算最低位的1的位置

    int lowbit(int x) {

        return x & (-x);

    }

};

int main() {

    int n;

    cin >> n;

    vector<int> arr(n);

    vector<pair<int, int>> values(n);

    for (int i = 0; i < n; i++) {

        cin >> arr[i];

        values[i] = make_pair(arr[i], i);

    }

    // 按照键排序

    sort(values.begin(), values.end());

    // 创建重映射数组

    vector<int> mapping(n);

    for (int i = 0; i < n; i++) {

        mapping[values[i].second] = i + 1;

    }

    // 创建树状数组

    BIT bit(n);

    long long count = 0;

    // 从右往左遍历原始数组

    for (int i = n - 1; i >= 0; i--) {

        int pos = mapping[i];  // 获取当前元素在排序后的序列中的位置

        count += bit.query(pos - 1);  // 获取比当前元素小的元素的计数

        bit.update(pos, 1);  // 当前元素出现一次，更新计数

    }

    cout << count << endl;

    return 0;

}