求逆序对个数的问题（即i<j的情况下，a[i]>a[j]的数据对个数），一般是把一组输入数据放到一个数组里，通过循环来计数。但是如果一组数据有很多（比如10^6）个，没办法开一个那么大的数组，应该用什么方法呢？

内存不够可以从堆空间申请资源(简单来说就是声明一个全局变量)
栈空间是连续的,通常申请资源的时候会找连续的一块,如果没有那么大的空间则不能分配内存~
堆空间是通过链表块来链接的,是不连续的,可以从操作系统申请资源分配,是不连续的,但可以申请的资源比较多~

两个for循环可能会超时,如果有需要的可以参考

https://bbs.bccn.net/viewthread.php?tid=485375&highlight=%D7%EE%B3%A4%B5%DD%D4%F6%D7%D3%D0%F2%C1%D0

大意就是说用o(log(n))的时间复杂度构建一个树状数组,然后看树状数组当前结点的深度,所有结点深度相加即是结果(或者那些oj平台的需要用到log long 型,不然10^6*10^6/2数据范围可能会有溢出)~

[此贴子已经被作者于2018-5-8 12:43编辑过]