C - Heap Like Sort

題目大意

小 Heap 拿到一塊方形板子，對角線(右上 $\leftrightarrow$ 左下) 上面有一些相異的數字。我們對於每一個小格給予定義：

• Open Cell: 這格是空的而且這格的左、上、左上方向的所有格子都是空的。
• Closed Cell: 這格是空的而且這格的右、下、右下方向的所有格子都是空的。
• Inner Cell: 所有其他的格子。
• Open-Only Cell: 這格是 Open cell 但是非 Closed cell。

小 Heap 開始對這個方形板子上的數字進行操作：

1. 如果現在有任何空的 Inner cell，我們查看它緊鄰右邊或下面的格子，如果有任何數字的話，挑選較小的那個，把它拉進來。
2. 如果現在不存在任何空的 Inner cell，那麼我們找一個 Open-Only Cell，滿足『這個 Open-Only Cell 緊鄰右邊和下面都不是 Open-Only Cell』。然後將這個 Open-Only Cell 緊鄰右邊或下面較小的那個數字搬上來。
3. 重複以上動作，直到動不了為止。

現在小 Heap 已經進行了一些操作，並且告訴你現在盤面的前 $n$ 列前 $m$ 行。請問當演算法停下來的時候，有數字的每一列，其長度為何？

範例輸入

6 6
0 0 0 0 0 5
0 0 0 0 2 0
0 0 0 3 0 0
0 0 1 0 0 0
0 6 0 0 0 0
4 0 0 0 0 0

移動過程舉例

我們用點取代 Closed cells，打 * 代表我們選擇那一格移動：

0 0 0 0 0 5     0 0 0 0 * 5     0 0 0 0 2 5
0 0 0 0 2 .     0 0 0 0 2 .     0 0 0 0 . .
0 0 0 3 . .     0 0 0 3 . .     0 0 0 3 . .
0 * 1 . . .  -> 0 1 . . . .  -> 0 1 . . . .
0 6 . . . .     0 6 . . . .     0 6 . . . . 
4 . . . . .     4 . . . . .     4 . . . . .

經過若干移動後會變成

1 2 5 . . .
3 6 . . . .
4 . . . . .
. . . . . .
. . . . . .
. . . . . .

所以輸出是

3
2
1

題解

這題基本上就是模擬題。對於這個題目，最有趣的一個性質是：無論你(依據規則)挑選空格的順序如何，操作完畢後必定有唯一的結果。這個有趣的遊戲叫做 Jeu de taquin。

我們來估計一下模擬所需要耗費的時間吧！稍微觀察一下，只要出現一個空的 Inner cell，就會一直把那個 Inner cell 「往右或往下推」。因此任何時間至多只有一個空的 Inner Cell。而且每一次從一個 Open-Only cell 開始，把這一格填滿並且透過一系列的 Inner cell 操作，這個空格只會被往右或往下推。所以每填一次空格會需要移動 $O(n+m)$ 個數字。

總共有 $nm$ 個格子，因此最大移動總量是 $O(nm(n+m))$ 這麼多次。

直接做的話...

如果我們每一次都重新計算 Open cell 與 Closed cell 的話，總共的時間會花費 $O(nm\times nm(n+m))\approx O(N^5)$ 我們用 $N$ 表示 $n+m$，這樣所花費的時間是 5 次方，顯然會 TLE。

更快的作法

由於隨時至多只有一個 Inner Cell，一開始我們可以花一點點時間把這個 Inner Cell 搞定。接下來，每一次隨意挑一個「可能滿足操作二的 Open-Only cell」，然後用類似 Heap 更新的方式(重複進行操作一) 處理這個 Inner Cell。

事實上，我們可以發現兩個重要的性質：

性質一

若過程出現空的行或列，我們可以直接把右邊(或下面)所有數字往左(或往上)搬移一格，等價於把該行或該列消除。

性質二

在任何一個時刻，如果不存在空的 Inner Cell，若我們觀察「有數字的地方」，它一定是「右上-左下漸進式的」。也就是說，每一列有數字的部份起始和結束的行數由上往下必定是不嚴格遞減的。

如何找到 Open-Only Cell?

很簡單，從右上開始，沿著所有 Open-Only Cell 的邊界(往左、或往下不斷前進)，就可以知道有沒有任何一個滿足條件的 Open-Only Cell 了。這部份花費的時間是 $O(N)$ 的。

時間複雜度?

一開始至多有 $O(nm)$ 個 Open-Only Cell，對於每一個「回合」，我們需要花 $O(N)$ 時間找到一個可以進行操作的 Open-Only Cell。接著我們花至多 $O(N)$ 個操作一移動它。

此外，若我們在過程中隨時發現一個空的行或空的列，立馬把所有數字搬一格將這個空行或空列消除（反正遲早要搬嘛！）

因此整個演算法的時間複雜度為 $O(nmN) \approx O(N^3)$，這樣就可以 AC 囉！

範例程式碼

待補完！