逆序對

排序是我學習演算法時無意間輕忽的一個問題，當然現實中存在非常多複雜的排序應用與議題，但在解題上總認為只要寫出 quick sort 就能應付一些基本的排序問題。實際上排序的問題還有好幾種變形，其中一種就是逆序對。

例題 A

$$2 \times N$$ 名編號為 $$1 \sim 2N$$ 的選手共進行 $$R$$ 輪比賽。每輪比賽開始前，以及所有比賽結束後，都會按照總分從高到低對選手進行一次排名。選手的總分為第一輪開始前的初始分數加上已參加過的所有比賽的得分和。總分相同的，約定編號較小的選手排名靠前。

每輪比賽的對陣安排與該輪比賽開始前的排名有關：第 1 名和第 2 名、第 3 名和第 4 名、......、第 $$2N - 1$$ 與 $$2N$$名各進行一場比賽。每場比賽勝者得 1 分，負者得 0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決於選手在之前比賽中的表現。

現給定每個選手的初始分數及其實力值，試計算在 $$R$$ 輪比賽過後，排名第 $$Q$$ 的選手編號是多少。我們假設選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。

2 4 2       // N, R, Q
7 6 6 7     // 起始分數
10 5 20 15  // 實力值

題解

這題其實跟逆序對無關，但跟未來逆序對解法有關，所以也順便提。這題直覺上的做法，會透過想透過排序演算法來模擬賽程。由於題目保證每個人的實力都是不同的，不會有重複值也不會變化，因此比賽的結果是完全可預期的。根據模擬的作法，首先我們在每次排序後，就按照題目的規則讓 $$2i$$ 與 $$2i+1$$ 的選手進行對戰，並讓勝利方的分數 $$+1$$，再依照分數排序選手的名次。

不過這個做法其實遇到大規模測資是會 TLE 的，由於大部分的排序演算法都是快速排序(quick sort)，此演算法在本題上有一個浪費之處，那就是其實我們在替選手計算分數時，已經完成了分組。

for (int i = 0; i < n; ++i) {
  int l = players[i * 2];
  int r = players[i * 2 + 1];
  int w = powers[l] > powers[r] ? l : r;
  int c = w == l ? r : l;
  winners[i] = w;
  losers[i] = c;
  ++scores[w];
}
int curr = 0;
int i = 0, j = 0;
while (i < n && j < n) {
  auto l = winners[i];
  auto r = losers[j];
  if (scores[l] > scores[r] || (scores[l] == scores[r] && l < r)) {
    players[curr++] = l;
    ++i;
  }
  else {
    players[curr++] = r;
    ++j;
  }
}
while (i < n) {
  auto l = winners[i++];
  players[curr++] = l;
}
while (j < n) {
  auto r = losers[j++];
  players[curr++] = r;
}

這裡的分組(divide)其實在我們提升勝組的分數時，就已經可以完成。快速排序雖然可以用在第一次比賽前，但之後的比賽再用快速排序，其實是浪費了分數計算時就已能完成的分治，因此在此題中使用 merge sort 是較為快速的一個選擇，名次高的勝組分數必定高於名次低的勝組、名次高的敗組分數必定高於名次低的敗組。因此快速排序並不是銀彈。

例題B

在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉。一個車站的職工發現橋的長度最多能容納兩節車廂，如果將橋旋轉180度，則可以把相鄰兩節車廂的位置交換，用這種方法可以重新排列車廂的順序。於是他就負責用這座橋將進站的車廂按車廂號從小到大排列。他退休後，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序。

4        // 車廂數量
4 3 2 1  // 車廂號碼

題解

這題歸類為入門題，對沒學過演算法的人來說，最快能想到的 bubble sort。只要每次交換就進行記錄就沒問題。不過其實這個問題有另一個寫法與另一種規模的測資。我們可以看看例題C。

例題C

給定一個正整數數列，請計算數列當中的逆序對總量。所謂逆序對即 $$a_i > a_j$$ 且 $$i < j$$。

6
5 4 2 6 3 1

測資答案為 11。

這題的解法之一就是 bubble sort，但以此題的測資規模是絕對行不通。但其實他有一個滿有趣的解法，同樣也是利用 merge sort。

void merge_sort(vector<int>& v, int lp, int rp, uint64_t& ans) {
  if (rp - lp <= 1)
    return;
  int mp = lp + (rp - lp) / 2;
  merge_sort(v, lp, mp, ans);
  merge_sort(v, mp, rp, ans);
  int i = lp;
  int j = mp;
  int k = lp;
  while (i < mp && j < rp) {
    if (v[i] <= v[j]) {
      tmp[k++] = v[i++];
    }
    else {
      tmp[k++] = v[j++];
      ans += mp - i;
    }
  }
  while(i < mp)
    tmp[k++] = v[i++];
  while (j < rp)
    tmp[k++] = v[j++];
  for (int i = lp; i < rp; ++i) {
    v[i] = tmp[i];
  }
}

此題的關鍵其實是在 ans += mp - i，這也是這個解法最費解的地方。我們可以思考一下這種狀況：

   p
3 4 1 2

在 merge sort 中，以 p 為分界的左右兩端子序列是已排序過的。在 merge 的階段，我們會分別從 3 4 與 1 2 各子序列的起點開始比較，再將元素放入暫存序列中。當我們 3 以 1 為對象比較時，滿足逆序對的定義 $$i < j, a_i > a_j$$，根據 merge sort 的分治規則，我們知道此時左子序列必為已排序的狀態，更直白地說：$$[i + 1, mp)$$ 的所有元素均不小於 $$a_i$$，因此意味著 $$[i, mp)$$ 的所有元素與 $$a_j$$ 之組合都必為逆序對，這就是 ans += mp - i 的來由。