公路交叉数（POJ3067）-树状数组解决逆序对
题目大意：
东海岸有N个城市，西海岸有M个城市（N≤1000，M≤1000），将建K条公路。每个海岸的城市从北到南编号为1,2，…每条高速公路都是直线，连接东海岸和西海岸的城市。建设资金由高速公路之间的交叉数决定。两个高速公路最多在一个地方交叉。请计算告诉公路之间的交叉数量。
输入：
输入以T开始，表示测试用例的数量。
每个测试用例都是3个整数N、M、K。
下面的K行每一行都包含两个数字，表示高速公路连接的城市号。第一个数是东海岸的城市号，第二个数字是西海岸的城市号。
输出：
对每个测试用例都输出“Test case x:s”，x表示输入样例编号，s表示交叉数。
输入样例：
1
3 4 4
1 4
2 3
3 2
3 1
输出样例：
Test case 1:5
题解：
根据样例，一共有5个交叉点，如下图
我们探讨一下怎么产生的交叉点，如果两边的城市都是以升序（降序）出现，我们发现就不会产生交叉点。
例如，1 2 和 2 3 就不会产生交叉点。
1 4 2 3就会产生交叉点，因为西海岸城市1、2是升序的，东海岸城市4、3是降序的。因此产生交叉和逆序对有关系。
通过上面分析，求交叉的数量，就是把公路两端的城市号，一端升序排列，另一端求逆序对的个数。
算法设计：
1、对数的边按照x升序排列，若x相等，则按有升序排列。
2、检查每条边i，统计y的前缀和sum（e[i].y）,该前缀和是前面比y小的正序数，即可得到逆序数为i-sum（e[i].y)，也就是前面的边和第i条边产生交叉的个数，ans累加这个交叉个数。
3、将树状数组中的e[i].y的值加1。
算法图解：
1、对边排序结果：
1 4
2 3
3 1
3 2
1、