洛谷 P1908 求逆序对

归并排序求逆序对数目

#include <iostream>
#include <cstdio>
using namespace std;

unsigned long long result = 0;
int a[500001] = {0};
int cache[500001] = {0};

void sort(int l, int r){
    if (r <= l) return;
    if(r-l==1){
        if(a[l]>a[r]){
            int temp = a[l];
            a[l] = a[r];
            a[r] = temp;
            result++;
        }
        return;
    }
    int mid = (l + r) / 2;
    //[l, mid] && [mid+1, r]
    sort(l, mid);
    sort(mid + 1, r);
    int len = r - l + 1;
    int x = l, y = mid + 1;
    int pos = 0;
    while(x<=mid && y<=r){
        while (x <= mid && y <= r && a[x] <= a[y]) {
            pos++;
            cache[pos] = a[x];
            x++;
        }
        if (x <= mid && y <= r && a[x] > a[y]){
            pos++;
            cache[pos] = a[y];
            y++;
            result += mid-x+1;
        } 
        if(x>mid){
            while(y<=r){
                pos++;
                cache[pos] = a[y];
                y++;
            }
            break;
        }
        if(y>r){
            while (x<=mid) {
                pos++;
                cache[pos] = a[x];
                x++;
            }
            break;
        }
    }
    for (int i = l; i <= r; i++){
        a[i] = cache[i - l + 1];
    }
}

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    sort(1, n);
    cout << result;
    return 0;
}

树状数组+离散化求逆序对数目

#include <iostream>
#define MAXN 500001
using namespace std;

int n;
unsigned long long result = 0;
int a[MAXN] = {0};
int ft[MAXN + 1] = {0};

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

void update(int index, int val) {
    for (int i = index; i <= n; i = i + lowbit(i)) {
        ft[i] += val;
    }
}

int getSum(int index) {
    int result = 0;
    for (int k = index; k > 0; k -= lowbit(k)) {
        result += ft[k];
    }
    return result;
}

class entry {
    public:
     int id, val, rank;
} m[500001];

// Last Update: 2020-12-30
/* Quick Sort With CMP Start */
// Sort the element between [a+left, a+right)
// You need to implement the "compare" function.
// You'd better implement a strict inequality in the set.
// An example is given in pseudocode.
/*
bool compare(T A, T B){
    if(A precedes B){
        return true;
    }else{
        return false;
    }
}
*/
template <class T>
void quickSort(T* a, int left, int right, bool (*cmp)(T, T)) {
    T pivot = *(a + right - 1);
    int l = left, r = right - 1;
    while (l < r) {
        while (l < r && !cmp(pivot, a[l])) {  // a[l] >= pivot then continue
            l++;
        }
        while (l < r && !cmp(a[r], pivot)) {  // a[r] <= pivot then continue
            r--;
        }
        if (l != r) {
            T temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        } else {
            a[right - 1] = a[l];
            a[l] = pivot;
            quickSort(a, left, l, cmp);
            quickSort(a, l + 1, right, cmp);
        }
    }
}
/* Quick Sort With CMP End */

bool compare1(entry a, entry b){
    if (a.val < b.val) return true;
    if (a.val > b.val) return false;
    if (a.id < b.id) return true;
    return false;
}

bool compare2(entry a, entry b){
    if (a.id < b.id) return true;
    return false;
}



int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        m[i].id = i;
        m[i].val = a[i]; 
    }
    quickSort(m, 1, n + 1, compare1);
    for (int i = 1; i <= n; i++){
        m[i].rank = i;
    }
    quickSort(m, 1, n + 1, compare2);
    for (int i = n; i >= 1; i--) {
        update(m[i].rank, 1);
        result = result + getSum(m[i].rank - 1);
    }
    cout << result;
    return 0;
}