BZOJ 1692 [USACO2007 Dec] 隊列變換：後綴數組 + 貪心構造字典序最小序列

題目背景

農夫 John 有 N (≤ 30,000) 隻奶牛排成一隊，每隻牛用名字首字母（A-Z）表示。他可以重複操作：從原隊列首端或尾端牽出一頭牛，接到新隊列尾部。求所有可能得到的新隊列中，字典序最小的一個。輸出時每行 80 字符。

核心觀察：雙端隊列的字典序比較

設原序列為 S，每次可從左端（L）或右端（R）取字符。構造字典序最小序列的貪心策略：

每一步比較 S[L...R]（正序）與 S[R...L]（逆序）的字典序，取較小者對應的端點字符。

理由：當前選擇決定了結果序列的下一個字符。為了整體字典序最小，應讓當前字符盡可能小。比較正序與逆序剩餘串，本質是在比較「選左邊後的最佳續」與「選右邊後的最佳續」。

O(1) 比較：後綴數組 + 循環擴展

直接逐字符比較正逆序最壞 O(N²) 會超時。巧妙構造：

1. 將原字符串 S 複製一份反轉拼接：T = S + '#' + reverse(S)（# 為比所有字母小的分隔符）
2. 對 T 構建 後綴數組 SA 及 Rank 數組
3. 原串區間 [L, R] 的正序剩餘串對應 T 中位置 L 開始的後綴
   逆序剩餘串對應 T 中位置 2N - R 開始的後綴（反轉部分的映射）
4. 比較 Rank[L] 與 Rank[2N - R] 即可 O(1) 判斷字典序大小

算法流程

// 構造 T = S + '$' + reverse(S)
for (int i = 0; i < n; ++i) T[i] = S[i];
T[n] = 0; // 分隔符，比 'A' 小
for (int i = 1; i <= n; ++i) T[n + i] = S[n - i];

// 建立後綴數組 SA 和 Rank
build_sa(2*n + 1, 27); // 字符集大小 27 (A-Z + $)
for (int i = 0; i <= 2*n; ++i) Rank[SA[i]] = i;

// 貪心構造答案
int L = 0, R = n - 1;
while (L <= R) {
    if (Rank[L] < Rank[2*n - R]) {
        ans.push_back(S[L++]);
    } else {
        ans.push_back(S[R--]);
    }
}

// 輸出，每行 80 字符
for (int i = 0; i < ans.size(); ++i) {
    putchar(ans[i]);
    if ((i+1) % 80 == 0 || i == ans.size()-1) putchar('\n');
}

複雜度

• 後綴數組構建：O(N log N)（倍增算法）或 O(N)（SA-IS/DC3）
• 貪心構造：O(N)
• 總時間：O(N log N)，N=30,000 輕鬆通過
• 空間：O(N)

關鍵細節

1. 分隔符必須最小：確保正序後綴與逆序後綴比較時不會跨越邊界
2. Rank 數組含義：Rank[i] 表示以 i 開頭的後綴在所有後綴中的排名（越小字典序越小）
3. 映射公式驗證：原串 [L, R] 逆序對應反轉串中 [n-1-R, n-1-L]，在 T 中起始位置為 n+1 + (n-1-R) = 2n - R