求逆序对的个数
解题思路：解题思路和归并排序非常接近。
由上图可以知道，逆序对出现的情况共三种。一种是两个数都出现在分界线左边， 一种是出现在右边，还有一种是左右各出现一个。第三种比较麻烦的是找到对于右边的某一个数，左边共有多少个大于这个数的数，即对应某个数一定存在多少个逆序对。我们回想归并的过程，就能想起只要q[i] <= q[j], 左边的标记就会一直增大，直到找到q[i] > q[j]的数，又因为归并的过程都是先归并相邻的两个区间，归并之后的区间都是有序的，因此后面递归左区间和右区间上不会出现说本来属于右区间的数到了左区间里面。因此此时的逆序对的个数就是左区间上i标记后面的数的个数。num = mid - i + 1;