UVA 12299 RMQ with Shifts：線段樹單點更新應用

問題描述

維護一個動態數組，支持兩種操作：
1. query(L,R)：查詢區間最小值
2. shift(i1,i2,...,ik)：對指定索引循環左移，即 A[i1]←A[i2], ..., A[ik]←A[i1]

數據範圍：n ≤ 100,000，q ≤ 250,000，需快速 I/O。

線段樹設計

• 每個節點存儲區間最小值
• 單點更新：modify(pos, new_val) 遞歸更新葉節點並回溯維護
• 區間查詢：標準 RMQ 遞歸查詢

Shift 操作處理

解析字符串提取索引序列 idx[0..cnt-1]。保存首值 tmp = A[idx[0]]，依次將 A[idx[i]] = A[idx[i+1]] 並調用 modify，最後 A[idx[cnt-1]] = tmp 並更新。每次 shift 需 k 次單點更新，總複雜度 O(k log n)。

關鍵代碼片段

// 線段樹結構
struct SegTree {
    vector<int> mn;
    int n;
    SegTree(int _n): n(_n), mn(4*_n) {}
    void build(int o, int l, int r, const vector<int>& a) {
        if (l == r) { mn[o] = a[l]; return; }
        int mid = (l+r)/2;
        build(o*2, l, mid, a);
        build(o*2+1, mid+1, r, a);
        mn[o] = min(mn[o*2], mn[o*2+1]);
    }
    void modify(int o, int l, int r, int pos, int val) {
        if (l == r) { mn[o] = val; return; }
        int mid = (l+r)/2;
        if (pos <= mid) modify(o*2, l, mid, pos, val);
        else modify(o*2+1, mid+1, r, pos, val);
        mn[o] = min(mn[o*2], mn[o*2+1]);
    }
    int query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) return mn[o];
        int mid = (l+r)/2, res = INT_MAX;
        if (L <= mid) res = min(res, query(o*2, l, mid, L, R));
        if (R > mid) res = min(res, query(o*2+1, mid+1, r, L, R));
        return res;
    }
};

輸入解析技巧

操作字符串無空格，如 shift(2,4,5,7)。從第 6 字符開始解析，遇到 , 或 ) 結束當前數字。

複雜度

• 構建：O(n)
• Query：O(log n)
• Shift：O(k log n)，總操作數 ≤ 250,000，k 總和可控

本題是線段樹「單點更新 + 區間查詢」的教科書級應用，關鍵在於高效解析 shift 命令字符串並批量更新。