algo-aha

逆序数

用归并排序的归并过程来统计，逆序数=左子问题+右子问题+跨数组逆序数。为统计跨数组逆序数，从数组末开始，一旦左数组末的a[i]>右数组末的b[j]（逆序），就知a[i]>b[j]>=b[j-1]>=...>=b[0]，关于a[i]的跨组逆序数是j+1。或者从数组头开始，一旦右数组头的b[j]<左数组头的a[i]（逆序），就知b[j]<a[i]<=a[i+1]<=...<=a[n1]，关于b[j]的跨组逆序数是n1-i+1。

• https://leetcode.com/problems/reverse-pairs/

int reversePairs(vector<int>& nums) {
	return mergeSort(nums, 0, (int)nums.size() - 1);
}

int mergeSort(vector<int>& nums, int l, int h) {
	if (l >= h) return 0;
	int mid = l + (h - l) / 2;
	int ans = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, h);

	// 统计组间逆序数
	for (int j = mid + 1; j <= h; j++) {
		// nums[l..mid]中找第一个>2*nums[j]的i
		auto it = upper_bound(begin(nums) + l, begin(nums) + mid + 1, 2l * nums[j]);
		int i = it - begin(nums);
		ans += mid - i + 1;  // 位置[i..mid]与i逆序
	}
	merge(nums, l, mid, h);
	return ans;
}

// 归并已排序的 nums[l..mid] 和 nums[mid+1..h]
void merge(vector<int>& nums, int l, int mid, int h) {
	vector<int> merged(h - l + 1);
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= h) {
		if (nums[i] < nums[j]) {
			merged[k++] = nums[i++];
		} else {
			merged[k++] = nums[j++];
		}
	}
	while (i <= mid) merged[k++] = nums[i++];
	while (j <= h) merged[k++] = nums[j++];
	for (int k = 0; k < merged.size(); k++) {
		nums[l + k] = merged[k];
	}
}

每个数右边比它小的数有多少个

• https://leetcode.com/problems/count-of-smaller-numbers-after-self

vector<int> countSmaller(vector<int>& nums) {
    // 要看数的右边，所以不能移动数字，在索引数组idx上归并排序
    const int N = nums.size();
    vector<int> idx;
    for (int i = 0; i < N; i++) {
        idx.push_back(i);
    }
    vector<int> ans(N, 0);
    mergeSort(nums, idx, 0, N - 1, ans);
    return ans;
}

void mergeSort(vector<int> &nums, vector<int> &idx, int l, int r, vector<int> &ans) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, idx, l, mid, ans);
    mergeSort(nums, idx, mid + 1, r, ans);

    vector<int> merged(r - l + 1);
    // 两指针同向遍历，从两数组末端开始比较
    int i = mid, j = r, k = r - l;
    while (i >= l && j > mid) {
        if (nums[idx[i]] > nums[idx[j]]) {
            ans[idx[i]] += j - mid; // 位置[mid+1..j]与i逆序
            merged[k--] = idx[i--];
        } else {
            merged[k--] = idx[j--];
        }
    }
    while (i >= l) merged[k--] = idx[i--];
    while (j > mid) merged[k--] = idx[j--];
    for (int k = 0; k < merged.size(); k++) {
        idx[l + k] = merged[k];
    }
}

全局逆序数==相邻逆序数

• https://leetcode.com/problems/global-and-local-inversions/

bool isIdealPermutation(vector<int>& A) {
    // 全局逆序数==相邻逆序数，除了相邻、没有逆序，
    // 即max(A[0..i-2])<=A[i]
    int theMax = -1;
    for (int i = 2; i < A.size(); i++) {
        theMax = max(theMax, A[i-2]);
        if (theMax > A[i]) return false;
    }
    return true;
}