POJ 3067 Japan

　　本題東邊有N個城市，西邊有M個城市，現在欲蓋多條高速公路連接東西邊，求路線的交點數。

ps.不會有三邊共點的情形

struct city{

     int e;  // 存東邊城市編號

     int w;  // 存西邊城市編號

}

想法1：每次讀入(e,w)時(設第k次)就檢查(k-1)次之前所有情況，若city[k-1].e<city[k].e，則city[k-1].w>city[k].w才會有交點，反之。此算法為O(n^2)會TLE。

想法2: 可依e由小到大(若e相等則依w小到大排)將city[K]排序，此時將只討論city[k-1].e<city[k].e的情況，只要檢察前(k-1)次的w值大於第k次的w值的總和就是解答，但如果又用兩個for loop來跑又變成O(n^2)的算法，本題可簡化為求city[K]的逆序數，使用mergesort求逆序數(可參考UVa 10810)，此算法為O(nlgn)會AC。