问题描述：
不少人很爱玩游戏，例如 CS ⑨。 游戏设计也成为程序开发的热点之一，我们假设要设计破旧仓库之类的场景作为战争游戏的背景。仓库的地面会因为阳光从屋顶的漏洞或者窗口照射进来而形成许多光照区域和阴影区域。为了简单起见，假设不同区域的边界都是直线 ⑩， 我们把这些直线都叫做“光影线”，并且不存在三条光影线相交于一点的情况。
那么，如果我们需要快速计算某个时刻，在 X 坐标[ A， B] 区间的地板上被光影划分成多少块。如何才能写出算法来计算呢？
问题：如何快速计算某个时刻，在X[A,B]区间上的地板被光影划分成多少块？
这个问题需要先自己归纳寻找规律。由于不存在三直线交于一点的情况，一些情况可以不用考虑。题目要求的是在A，B区间内，通过尝试可以找到规律。如果只有一条线，那么分割成两块空间。如果有两条线，可能相交，也可能不相交（只要在A到B这个区间内不相交就行）。如果相交，那么就分割成四块，否则是三块。以此类推就会发现，分割块数=线的数量+在这个区间内的交点数量+1。
也就是说，只需要判断在这个区间内的交点有几个，经过这个区间的线有几条即可。我们可以先进行一次预处理，计算出所有交点的位置，然后在每一次查询时就可以很快查找到了。
解法一：
两条直线+一个交点=>空间分成4块
三条直线+2个交点=>空间分成6块
三条直线+3个交点=>空间分成7块
n条直线+m个交点=>空间分成n+m+1块
初始化时间复杂度O(N^2)，找出所有的交点
每次查询时间复杂度O(m)，哪些交点在X[A,B]区间内
若初始化后将交点按x轴排序，初始化需O(N^2+mlogm)
然后每次查询二分查找O(logm)
解法二：
可以看出图中的逆序数等于直线的交点数，因为没有3条直线相交于一个点。
直接求解逆序数的方法是O(N^2)
可以用分治的思想降为O(NlogN)，可通过归并排序或树状数组求得。
设A[1..n]是一个包含N个非负整数的数组。如果在iA[j]，则(i,j)就称为A中的一个逆序对(inversion)。
b)如果数组的元素取自集合｛1，2，...，n｝，那么，怎样的数组含有最多的逆序对？它包含多少个逆序对？
c)插入排序的运行时间与输入数组中逆序对的数量之间有怎样的关系？说明你的理由。
d)给出一个算法，它能用O(nlogn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目（提示：修改归并排序）
——《算法导论》，思考题2-4
问题b)为了逆序对最多，那么应使任一个数在所有比它小的数前面，从而构成所有可能逆序，即[n,n-1,...,1]，这样一共有(n-1)+(n-2) + ... + 1 =n(n-1)/2个。
1.在归并排序中，同样是对一个数组分为两段处理，在处理这两段时，并不会影响右段元素与左段元素的逆序关系，只有在归并时才会改变。
2.归并时的改变方式和插入排序是类似的：右段中取出元素放在左段其余所有元素前面时，相当于左段整体后移，后移的元素数就是这个逆序数。
3.由于归并排序使用的是分治法，将每次归并的逆序数累加，最后结果就是总的逆序数。并且，归并排序的时间复杂度是O(nlogn)，优于插入排序。
求逆序数当然也可以利用分治思想去解决。对于数组a1,a2,a3............aN，将数组分为两个子问题求解，分别求解a1,a2.....a(1+N)/2的逆序数，和a(3+N)/2的逆序数，然后再求解两个子数组之间形成的逆序数。这里就要用到归并排序了，这里假设左边和右边的子数数组经过递归以后已经是有序的了（只有一个元素时子数组逆序数为1），然后将两个子数组合并，对于右边子数组中的每个元素，当这个元素加到临时数组中时，只要求出左边比它大的元素个数是多少就可以了，然后将所有这个个数相加既是答案。左边比该元素大的元素个数为mid-i+1,i为左边数组此时的下标。
6 | int Merge(int* a,int low,int mid,int high){ |
9 | int* tmp=(int*)malloc(sizeof(int)*(high-low+1)); |
10 | while(i<=mid&&j<=high){ |
23 | memcpy(a+low,tmp,sizeof(int)*(high-low+1)); |
28 | int Inversion(int* a,int low,int high){ |
29 | int n1=0 ,n2=0 ,n3=0 ; |
32 | n1 = Inversion(a,low,mid); |
33 | n2 = Inversion(a,mid+1,high); |
34 | n3 = Merge(a,low,mid,high); |
方法二：线段树+离散化
这道题目可以利用线段树去做，我们知道线段树处理区间问题是比较方便的，效率也很高，所以线段树也叫区间树，但是这道题目0<=a[i]<999999999,但是共有不超过500000个数据，所以很显然要用到数据的离散化，所谓离散化就是将数据映射到排序后它的下表，即它是第几小的。离散化之后存入数组hash,然后将数组中每个数插入到线段树中，并且ans加上区间(hash[i]+1,N)的值
方法三：树状数组
从上面可以看到，利用线段树编码量大，编码难度高，浪费内存，而且运行效率并不高。所以，自然而然可以想到用树状数组去做，树状数组做法和线段树做法极其相似，这里不做详述。
已知平面内有n条直线，这n条直线有m个交点（p条直线交于一点时，交点数计p-1）。则这n条直线把这个平面分成了n+m+1个平面。
这个定理的推论如下：
已知平面内有n条直线，则这n条直线最多可以把平面分成1+n+
更为优雅的一种写法是：
http://hi.baidu.com/zealot886/item/1e49e93ed3669f03cfb9fe71
一道Hulu的笔试题:N条直线最多将平面划分为多少区域，如果换成折线，又是多少?
参考《编程之美》1.7节“光影切割问题”，下面是我的解答：
由上图可知：
两条直线最多一个交点，将平面分成了4个区域；
三条直线最多三个交点，将平面分成了7个区域；
可以推出：
每增加一条直线，如果增加m个交点，那么这条直线被新增加的m个交点，分成（m+1）段。每一段又会将原来的一个区域分成两块，因此，新增加了（m+1）个新区域。增加第N+1条直线时，最多与前面N条直线全部相交，增加n个交点。因此，最多增加n+1个区域。由此可得递推式：
解得：
如果换成折线呢？
增加第N+1条折线时，最多与前面的N条折线有 个交点，最多增加4n+1个区域，递推式为：
解得：
这里首先用到了一个数学定理：
