[Classic Question] Number of reverse order pairs Discrete techniques

P1908 Reverse order pair

Reverse order pair

Question description

The reverse order pair is in the sequence\(a_i>a_j\)and\(i<j\)Orderly pairs.
The time complexity of the following solutions is\(O(log n)\)

Combination and treatment method

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

int help[500005];

long long merge(vector<int>& arr, int l, int m, int r) {
	long long ans = 0;
	for (int i = m, j = r; i >= l; i--) {
		while (j > m && arr[i] <= arr[j]) {
			j--;
		}
		ans += j - m;
	}
	int i = l, a = l, b = m+1;
	while (a <= m && b <= r) {
		help[i++] = arr[a] < arr[b] ? arr[a++] : arr[b++];
	}
	while (a <= m) {
		help[i++] = arr[a++];
	}
	while (b <= r) {
		help[i++] = arr[b++];
	}
	for (int i = l; i <= r; i++) {
		arr[i] = help[i];
	}
}

long long f(vector<int>& arr, int l, int r) {
	if (l == r) {
		return 0;
	}
	int mid = (r - l) / 2 + l;
	return f(arr, l, m) + f(arr, m+1, r) + merge(arr, l, m, r);
}

int main() {
	
	return 0;
}

Tree-like array solution

First of all, the reverse order pair is to traverse a number to see how many of the numbers behind it are larger than him, so you can traverse from right to left and count\([1, x-1]\)The word frequency of word frequency requires a single point of modification every time you traverse to a new number, and query the prefix sum with the range. Therefore, select a tree-like array and notice that the data range is too large. If it is not processed, it will be achieved.\(10^9\). What is certain is that we do not need specific numerical sizes, we only need relative sizes, so we can process discretely.
The specific processing is as follows:Sort the original data from small to large, and its subscript is the new value, and then brush the value back into the array, so as to transfer the value range from\(10^9\)Reduced to the order of magnitude consistent with the array size, and ensures the relative size of the data

Process the original data to ensure that the new value is not less than 1

void transfer() {
    sort(arr+1, arr+n+1);
    len = 1;
    for (int i = 2; i <= n; i++) {
        if (arr[len] != arr[i]) arr[++len] = arr[i];
    }
    for (int i = 1; i <= n; i++) {
        sorted[i] = lower_bound(arr+1, arr+1+len, sorted[i]) - arr;
    }
}

Total code

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

const int MAXN = 5e5+7;
int n;
int arr[MAXN];
int sorted[MAXN];
int tree[MAXN];
int len;
void transfer() {
    sort(arr+1, arr+n+1);
    len = 1;
    for (int i = 2; i <= n; i++) {
        if (arr[len] != arr[i]) arr[++len] = arr[i];
    }
    for (int i = 1; i <= n; i++) {
        sorted[i] = lower_bound(arr+1, arr+1+len, sorted[i]) - arr;
    }
}

void add(int i, int v) {
    while (i <= n) {
        tree[i] += v;
        i += i & (-i);
    }
}

long long sum(int i) {
    long long ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= i & (-i);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0), (0), (0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sorted[i] = arr[i];
    }
    transfer();
    long long ans = 0;
    for (int i = n; i > 0; i--) {
        int x = sorted[i];
        ans += sum(x-1);
        add(x, 1);
    }
    cout << ans << "\n";
    
    return 0;
}