a457: TOI2010 第五題：餐廳評鑑

a457: TOI2010 第五題：餐廳評鑑

 題 目:

 簡 單 來 說 就 是 ，給 你 兩 組 數 列 A, B，請 求 出 滿 足 

 ( A[i] < A[j] 且 B[i] > B[j] ) 或 ( A[i] > A[j] 且 B[i] < B[j] ) 且 ( i < j ) 條 件 的 數 對 個 數。

 5 <= A, B 的 長 度 <= 10^5

 solve: 

 一 開 始 想 法 是 暴 力，但 是 看 到 了 A, B 的 長 度 就 想 說 不 太 可 能 用 暴 力 過，

 所 以 就 換 了 另 一 種 想 法。

 如 果 ( A[i] > A[j] 且 B[i] < B[j] ) 的 A[i], A[j] 跟 B[i], B[j] 互 換 那 不 就 變 成  

 ( A[i] < A[j] 且 B[i] > B[j] )，互 換 後 其 實 不 影 響 配 對 數 ， 因 為 最 終 決 定 的 是

 對 應 的 數 列 B。

 互 換 後 條 件 就 剩 下 B[i] > B[j] ( i < j ) 即 是 逆 序 數 對 個 數，逆 序 對 可 以 用 一 次

 merge sort 求 出。

code: