Memory of Cutey

昨天，上海下了今年入冬以来的第一场雪。有人说，“一切不以下雪为目的的刮风和降温都是耍流氓”，北京一直在耍流氓，上海倒是蛮实在的。 前天还在享受冬日的阳光明媚，一夜之间温度骤降至零下，到了中午天空中竟开始飘起雪花，随即越来越大，渐渐也积起薄薄的一层，让来不及抱怨寒冷的人们收获了意外的惊喜。 南方给人的感觉一直是温婉的，就连雪也是一样，虽比不上北国风光，千里冰封，万里雪飘的壮阔，却也似银装素裹，别有一番风情。

简介：归并排序(merging sort)的时间复杂度为O(nlogn)，是一种稳定的排序方法。常用的2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，递归算法形式简洁，简单易用。 应用1：求逆序对数 设a[1...n]是一个包含n个不同数的数组，对于i<j如有a[i]>a[j]，则称(i,j)为一个逆序对。出题方式很多，比如直接求一个序列中逆序对的个数；比如交换原序列中相邻两元素位置使之成为单调不下降序列，求交换次数等等。当然，求逆序对数的方法也很多，但时间复杂度不大于O(nlogn)就只有归并排序和平衡二叉树了吧，显然归并排序实现起来更加简单，代码如下所示。 #include <stdio.h> #define MAX 50001 int temp[MAX]; int count, n; void Merge(int *array, int s, int m, int t) { int i=s, j, k; for (j=m+1,k=s; s<=m&&j<=t; ++k) { if (array[s]<=array[j]) temp[k] = array[s++]; else { temp[k] = array[j++]; count += m-s+1; //record the inversion pairs } } while (s<=m) temp[k++] [...]