题目描述（POJ3067）： 东海岸有 N 个城市，西海岸有 M 个城市（ N ≤1000， M ≤1000），将建成 K 条高速公路。每个海岸的城市从北到南编号为1, 2, ……每条高速公路都是直线，连接东海岸的城市和西海岸的城市。建设资金由高速公路之间的交叉数决定。两个高速公路最多在一个地方交叉。请计算高速公路之间的交叉数量。

输入： 输入文件以 T 为开头，表示测试用例的数量。每个测试用例都以3个数字 N 、 M 、 K 为开头。下面 K 行中的每一行都包含两个数字，表示由高速公路连接的城市号。第1个是东海岸的城市号，第2个是西海岸的城市号。

输出： 对每个测试用例，都单行输出“Test case x : s ”， x 表示输入样例编号， s 表示交叉数。

题解： 根据输入样例分析，一共有5个交叉点。

那么，怎么求交叉点呢？首先搞清楚交叉点是怎么产生的。当两条边的城市号都以升序（或降序）形式出现时，不产生交叉点。例如1 2和2 3不会产生交叉点。

1 4和2 3会产生交叉点，因为西海岸城市1、2是升序的，东海岸城市4、3是降序的。

因此交叉点的产生原因和逆序对有关系，所以转变为求解逆序对问题。

1. 算法设计

（1）对输入的边按照 x 升序排列，若 x 相等，则按 y 升序排列。

（2）检查每条边 i ，统计 y 的前缀和sum(e[ i ]. y )，该前缀和是前面比 y 小的正序数，边数减去正序数，即可得到逆序数 i -sum(e[ i ]. y )，ans累加逆序数。

（3）将树状数组中e[ i ]. y 的值加1。

2. 完美图解

根据输入样例，其交叉点求解过程如下。

（1）对输入的边按照 x 升序，若 x 相等，则按 y 升序。

排序结果：

（2）按照排序结果检查每条边 i ，统计 y 的前缀和sum(e[ i ]. y )，将ans累加 i -sum(e[ i ]. y )。

· i =0：1 4=。sum(4)0， i -sum(4)=0；1的前缀和为0，说明1前面没有数，因为前面还没有输入边，所以逆序边数量ans=0。

· i =1：2 3。sum(3)=0， i -sum(3)=1。3的前缀和为0，说明3前面没有数，所以前面的1条边是逆序的，当前边和逆序边会产生交叉点，累加逆序边数量ans=1。

· i =2：3 1。sum(1)=0， i -sum(1)=2。1的前缀和为0，说明1前面没有数，因此前面的两条边是逆序的，当前边和每条逆序边会产生交叉点，累加逆序边数量ans=3。

· i =3：3 2。sum(2)=1， i -sum(2)=2；前面的3条边已经有1条边是正序的，将该边减去，其余两条边是逆序的，当前边和每个逆序边都会产生交叉点，累加逆序边数量ans=5。 J+wuqlypzSHLD9VdjYiTC6ZtkdRZFp8AGwU6XzEZbKsJ/UW+sGzQrvvxd4pGklzZ

3. 算法实现