這是一個典型的演算法題目，它看似簡單，但藏著對效能要求的陷阱。直接按照題意模擬會超時，需要我們找出問題的內在規律，設計更聰明的演算法。

1. 問題分析與規則簡化 🧐

首先，我們重新檢視選擇廁所的三條規則：

1. 選擇 min(i-Li, Ri-i) 最大者。
2. 若規則 1 無法決定，選擇 max(i-Li, Ri-i) 最大者。
3. 若規則 2 仍無法決定，選擇編號 i 最小者。

這三條規則聽起來有點複雜，但我們可以把它們簡化。想像一下，一個空廁所區間由左右兩個已佔用的人 L 和 R 界定。

• 規則 1 (最大化最小距離) 的意思是，人會選擇最靠近區間正中央的位置，這樣他離左右兩邊的最小距離才會是最大的。
• 規則 2 (最大化最大距離) 在這種情況下，也是選擇讓區間更均勻分割的位置。
• 規則 3 (選擇編號小者) 則是在所有條件都相同時，選擇最靠左的。

將這三條規則結合起來，我們可以得到一個非常清晰的核心策略：

在任何時候，下一個人永遠會選擇當下「最長的連續空廁所區間」，並坐到該區間的正中央。如果存在多個長度相同的最長區間，他會選擇最靠左的那一個。

2. 最初的想法與陷阱：直接模擬 🐢

最直觀的想法就是完全按照上面的核心策略來模擬。

1. 用一個資料結構（例如 Java 的 PriorityQueue）來儲存所有「空的區間」。
2. 這個 PriorityQueue 的排序規則就是我們的核心策略：優先按區間長度由大到小排序；如果長度相同，則按起始位置由小到大排序。
3. 寫一個迴圈，從第 3 個人開始，一直模擬到第 k 個人。在每次迴圈中：
   • 從 PriorityQueue 取出最優的區間。
   • 計算其中點，這就是這個人坐的位置。
   • 將這個區間分裂成兩個較小的子區間，再放回 PriorityQueue 中。

這個方法哪裡有問題？

答案是效能。題目給的限制是 n 和 k 最大可達 1018。一個一個模擬 k 次的迴圈，當 k 是天文數字時，程式絕對會跑到天荒地老，導致超時 (Time Limit Exceeded)。

因此，我們需要一種方法，能夠「快轉」這個模擬過程。

3. 高效的策略：「計數與跳躍」模擬 🚀

既然不能一個一個模擬，我們可以一次「跳過」一大批人。關鍵點在於，所有長度相同的最長區間，在被更短的區間考慮之前，一定會被優先填滿。

這啟發了我們的「計數與跳躍」 (Count and Skip) 策略：

第一階段：快速跳躍，確定目標區間的屬性

我們不需要知道每個區間的具體位置，只需要追蹤**「不同長度的區間各有多少個」**。

1. 資料結構：使用 TreeMap<長度, 數量>。TreeMap 可以自動幫我們把「長度」這個鍵 (key) 排序，我們設定它由大到小排序，這樣每次都能輕易拿到最長區間的資訊。

2. 模擬迴圈：

   • 初始狀態：第 1、2 個人佔據了 1 和 n。我們剩下一個長度為 n-1 的大區間 (1, n)。TreeMap 裡是 { n-1: 1 }。我們要處理剩下 k-2 個人。
   • 迴圈開始：從 TreeMap 中取出最長的區間長度 L 和其數量 C。
   • 判斷：
     • 如果 k-2 <= C：太好了！這表示我們要找的第 k 個人，就是這 C 個長度為 L 的區間中，從左到右數過來的第 k-2 個。我們的目標已經鎖定，跳躍階段結束。
     • 如果 k-2 > C：表示這 C 個長度為 L 的區間會全部被填滿，但還輪不到我們要找的人。我們就「跳過」這 C 個人，讓 k-2 -= C。
   • 分裂：既然跳過了，就要把這 C 個長度為 L 的區間分裂成子區間。每個長度 L 的區間會分裂成兩個長度為 L/2 和 L - L/2 的子區間。我們將這些新的子區間數量更新回 TreeMap 中，繼續下一輪迴圈。

經過這個階段，我們會得到兩個重要資訊：

1. 目標長度 (target_len)：我們要找的人所進入的區間長度。
2. 目標順位 (rank)：在所有同長度的區間中，我們要找的那個是從左到右數過來的第幾個。

4. 最後一哩路：遞迴定位 🎯

現在我們知道目標區間的「長相」，但不知道它在「哪裡」。這時就需要第二階段：從頭開始，遞迴地尋找這個特定區間的位置。

我們設計一個函式 findLocation(l, r, target_len, rank)，它的任務是在 (l, r) 這個範圍內，找到長度為 target_len 且順位為 rank 的區間。

1. 遞迴邏輯：

   • 在當前 (l, r) 區間，我們先把它分裂成左、右兩個子區間 (l, mid) 和 (mid, r)。
   • 我們計算左邊的子區間 (l, mid) 總共會產生多少個符合 target_len 的區間 (這裡需要另一個輔助的遞迴函式 countIn 來計算，並且用快取/記憶化來加速)。
   • 判斷：
     • 如果 rank 小於等於左邊的計數，表示我們的目標在左子區間裡，我們就遞迴進入 findLocation(l, mid, ...)。
     • 如果 rank 大於左邊的計數，表示目標在右子區間裡。我們遞迴進入 findLocation(mid, r, ...)，並且把 rank 減去左邊的計數 (rank -= count_from_left)。

2. 遞迴終點：當 findLocation 的 (l, r) 區間長度剛好等於 target_len 時，表示我們已經找到了這個區間！直接計算它的中點 l + (r-l)/2 就是最終答案。

總結

這個解法結合了多種演算法思想：

• Greedy (貪心)：核心策略是每次都選最優（最長）的區間。
• 高效模擬：「計數與跳躍」讓我們避免了不必要的單步計算。
• 分治與遞迴：findLocation 和 countIn 函式都使用了遞迴，將大問題分解為小問題來求解。
• 記憶化 (Memoization)：用 cache 來儲存 countIn 的計算結果，避免對相同區間進行重複的昂貴計算。

透過這樣的層層分析與優化，我們就能寫出一個既正確又高效的程式，來解決這個看似棘手的問題。