HDU 4630 No Pain No Game：線段樹離線處理區間最大公約數查詢

題目轉化

給排列，q 次區間查詢：區間內任意兩數的最大公約數。等價於：找最大的 d，使區間內至少有兩個數是 d 的倍數。

離線處理策略

1. 預處理每個數的所有約數
2. 查詢按右端點 r 排序
3. 掃描數組，維護每個約數最近出現位置
4. 當約數再次出現，在前一位置更新線段樹：該約數作為候選值
5. 查詢時取區間最大值

線段樹維護

• 單點更新：update(pos, val) 取最大
• 區間查詢：query(L, R) 返回最大值
• 離線保證：處理到 r 時，所有 ≤r 的信息已就緒

關鍵代碼邏輯

for (int i = 1; i <= n; ++i) {
    for (int d : divisors[a[i]]) {
        if (last[d]) seg.update(last[d], d);  // 前一位置標記此約數
        last[d] = i;
    }
    while (q_idx < Q && queries[q_idx].r == i) {
        ans[queries[q_idx].id] = seg.query(queries[q_idx].l, i);
        ++q_idx;
    }
}

複雜度分析

約數枚舉 O(n √MAXA)，排序 O(q log q)，線段樹操作 O((n+q) log n)。總體 ~10⁷ 操作，1秒內輕鬆通過。

關鍵優化

• 約數預計算用篩法 O(MAXA log MAXA)
• 線段樹只存最大值，無需懶標記
• 離線轉換將二維區間問題降為一維掃描