HDU 4630 No Pain No Game 線段樹 區間最大 GCD

問題

1..n 的排列，Q 次查詢 [l,r]，求區間內任意兩個不同數的最大 GCD。n,Q ≤ 50,000。

關鍵洞察：因數視角

兩數 GCD ≥ d ⇔ 兩數都是 d 的倍數。區間內若有 ≥2 個 d 的倍數，則答案 ≥ d。最大 GCD = 最大的滿足條件的 d。

離線處理 + 線段樹

1. 對每個數預計算所有因數
2. 按右端點 r 排序查詢
3. 掃描 i=1..n，維護每個因數 d 最近出現的兩個位置 last1[d], last2[d]
4. 當 last2[d] 更新時，在線段樹位置 last2[d] 更新值 d（表示以此為右端點時 d 可行）
5. 查詢 [l,r]：線段樹查 [l,r] 最大值即答案

線段樹維護區間最大值

struct SegTree {
    vector<int> t;
    int n;
    SegTree(int n): n(n), t(4*n, 0) {}
    void update(int p, int v) { update(1,1,n,p,v); }
    void update(int u, int l, int r, int p, int v) {
        if (l==r) { t[u]=max(t[u],v); return; }
        int mid=(l+r)>>1;
        if (p<=mid) update(u<<1,l,mid,p,v);
        else update(u<<1|1,mid+1,r,p,v);
        t[u]=max(t[u<<1], t[u<<1|1]);
    }
    int query(int L, int R) { return query(1,1,n,L,R); }
    int query(int u, int l, int r, int L, int R) {
        if (L<=l && r<=R) return t[u];
        int mid=(l+r)>>1, ans=0;
        if (L<=mid) ans=max(ans, query(u<<1,l,mid,L,R));
        if (R>mid) ans=max(ans, query(u<<1|1,mid+1,r,L,R));
        return ans;
    }
};

掃描邏輯

vector<vector<int>> divisors(n+1);
for (int i=1;i<=n;++i)
    for (int j=i;j<=n;j+=i)
        divisors[j].push_back(i);

vector<int> last1(n+1,0), last2(n+1,0);
SegTree st(n);
sort(queries.begin(), queries.end(), [](auto&a,auto&b){return a.r

複雜度

因數預處理：O(n log n)
掃描：每個數約 log n 個因數，總更新 O(n log n log n)
查詢：O(Q log n)
總體 O((n+Q) log² n)，通過 5e4 限制