题目P1908 逆序对 - 洛谷归并排序的基本原理归并排序是一种分治算法其核心思想是将大问题分解为小问题解决小问题将小问题的解合并成大问题的解排序的关键作用高效计算跨越逆序对排序重要性体现在当左半部分和右半部分各自有序时如果发现a[cur1] a[cur2]那么由于左半部分是有序的所以从cur1到mid的所有元素都大于a[cur2]因此可以一次性计算出mid - cur1 1个逆序对如果没有排序我们就无法做出这个推断只能逐个比较// 如果没有排序需要这样计算效率低下 for (int i cur1; i mid; i) { if (a[i] a[cur2]) ret; }这样时间复杂度会从O(n log n)退化为O(n²)。为什么排序 不影响逆序对统计关键点逆序对是由元素的值决定的而不是由元素的位置决定的。我们确实在改变元素的物理位置排序但统计时机不同我们在排序之前就已经统计了所有逆序对这是分层统计的智慧。递归过程中的三个阶段统计左半部分内部的逆序对在递归调用dfs(left, mid)中完成统计右半部分内部的逆序对在递归调用dfs(mid1, right)中完成统计跨越左右的逆序对在当前合并步骤中完成关键理解排序发生在统计之后dfs(left, mid); // 先统计左半部分的逆序对dfs(mid1, right); // 再统计右半部分的逆序对// 然后才进行排序和合并重要在排序发生之前所有内部逆序对左半部分内部和右半部分内部已经被统计并记录在ret中了#include iostream using namespace std; const int N 1e6 10; int a[N]; int tmp[N]; typedef long long LL; LL ret 0; LL dfs(int left, int right) { if (left right) return 0; int mid (left right)/2; dfs(left, mid); dfs(mid1, right); int cur1 left, cur2 mid1, i left; //i 指向临时数组tmp的当前位置用于存放合并后的元素 while(cur1 mid cur2 right) { if (a[cur1] a[cur2]) tmp[i] a[cur1]; // 如果左半部分的当前元素小于等于右半部分的当前元素 // 将左半部分的元素放入临时数组 // 左指针cur1和临时数组指针i都向后移动一位 else { ret mid-cur11; tmp[i] a[cur2]; // 如果左半部分的当前元素大于右半部分的当前元素 计算逆序对 // 将右半部分的元素放入临时数组 // 右指针和临时数组i都向后移动一位 } } // 如果左半部分还有剩余元素将它们全部复制到临时数组 while(cur1 mid) tmp[i] a[cur1]; // 如果右半部分还有剩余元素将它们全部复制到临时数组 while(cur2 right) tmp[i] a[cur2]; // 将临时数组中已排序的元素复制回原数组a的相应位置 // 这样原数组的[left, right]区间就变成了有序的 for (int i left; i right; i) a[i] tmp[i]; return 0; } int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; dfs(1, n); cout ret endl; return 0; }cur1为什么不用回到 l ?如果cur1这个位置小于等于cur2这个位置cur1往下走一步就行了赋值数组。但是如果cur1数 cur2树cur2往下走一步赋值数组。cur1为什么不用回到起点呢数组是升序排序cur1走过来的时候cur1前面的1,2是小于cur2这个数的。cur2这个数变大了cur1前面的1,2肯定还是小于cur2。所以不用回到原点。细节问题为什么 i 是赋值成l 限定条件是 r在归并排序中我们不是一次性处理整个数组而是递归地处理不同的子区间for (int i left; i right; i) a[i] tmp[i];只处理数组当前的部分。求mid必须是 (leftright)/2中点mid必须确保每次递归调用都将区间分割成更小的子区间从而逐步逼近终止条件。标准做法mid (left right) / 2通过整数除法向下取整。如果使用 int mid (left right1) / 2; 是错误的会造成TLE。
分治：逆序对
题目P1908 逆序对 - 洛谷归并排序的基本原理归并排序是一种分治算法其核心思想是将大问题分解为小问题解决小问题将小问题的解合并成大问题的解排序的关键作用高效计算跨越逆序对排序重要性体现在当左半部分和右半部分各自有序时如果发现a[cur1] a[cur2]那么由于左半部分是有序的所以从cur1到mid的所有元素都大于a[cur2]因此可以一次性计算出mid - cur1 1个逆序对如果没有排序我们就无法做出这个推断只能逐个比较// 如果没有排序需要这样计算效率低下 for (int i cur1; i mid; i) { if (a[i] a[cur2]) ret; }这样时间复杂度会从O(n log n)退化为O(n²)。为什么排序 不影响逆序对统计关键点逆序对是由元素的值决定的而不是由元素的位置决定的。我们确实在改变元素的物理位置排序但统计时机不同我们在排序之前就已经统计了所有逆序对这是分层统计的智慧。递归过程中的三个阶段统计左半部分内部的逆序对在递归调用dfs(left, mid)中完成统计右半部分内部的逆序对在递归调用dfs(mid1, right)中完成统计跨越左右的逆序对在当前合并步骤中完成关键理解排序发生在统计之后dfs(left, mid); // 先统计左半部分的逆序对dfs(mid1, right); // 再统计右半部分的逆序对// 然后才进行排序和合并重要在排序发生之前所有内部逆序对左半部分内部和右半部分内部已经被统计并记录在ret中了#include iostream using namespace std; const int N 1e6 10; int a[N]; int tmp[N]; typedef long long LL; LL ret 0; LL dfs(int left, int right) { if (left right) return 0; int mid (left right)/2; dfs(left, mid); dfs(mid1, right); int cur1 left, cur2 mid1, i left; //i 指向临时数组tmp的当前位置用于存放合并后的元素 while(cur1 mid cur2 right) { if (a[cur1] a[cur2]) tmp[i] a[cur1]; // 如果左半部分的当前元素小于等于右半部分的当前元素 // 将左半部分的元素放入临时数组 // 左指针cur1和临时数组指针i都向后移动一位 else { ret mid-cur11; tmp[i] a[cur2]; // 如果左半部分的当前元素大于右半部分的当前元素 计算逆序对 // 将右半部分的元素放入临时数组 // 右指针和临时数组i都向后移动一位 } } // 如果左半部分还有剩余元素将它们全部复制到临时数组 while(cur1 mid) tmp[i] a[cur1]; // 如果右半部分还有剩余元素将它们全部复制到临时数组 while(cur2 right) tmp[i] a[cur2]; // 将临时数组中已排序的元素复制回原数组a的相应位置 // 这样原数组的[left, right]区间就变成了有序的 for (int i left; i right; i) a[i] tmp[i]; return 0; } int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; dfs(1, n); cout ret endl; return 0; }cur1为什么不用回到 l ?如果cur1这个位置小于等于cur2这个位置cur1往下走一步就行了赋值数组。但是如果cur1数 cur2树cur2往下走一步赋值数组。cur1为什么不用回到起点呢数组是升序排序cur1走过来的时候cur1前面的1,2是小于cur2这个数的。cur2这个数变大了cur1前面的1,2肯定还是小于cur2。所以不用回到原点。细节问题为什么 i 是赋值成l 限定条件是 r在归并排序中我们不是一次性处理整个数组而是递归地处理不同的子区间for (int i left; i right; i) a[i] tmp[i];只处理数组当前的部分。求mid必须是 (leftright)/2中点mid必须确保每次递归调用都将区间分割成更小的子区间从而逐步逼近终止条件。标准做法mid (left right) / 2通过整数除法向下取整。如果使用 int mid (left right1) / 2; 是错误的会造成TLE。
