POJ 3580 SuperMemo：Splay 樹區間操作（翻轉、循環移位、插入、刪除、區間加、區間最小值）

問題描述

初始序列長度 n (≤ 100000)，支持 M (≤ 100000) 次操作：

• ADD x y D：區間 [x, y] 每個數加 D。
• REVERSE x y：區間 [x, y] 反轉。
• REVOLVE x y T：區間 [x, y] 向右循環移位 T 次。
• INSERT x P：在位置 x 後插入 P。
• DELETE x：刪除位置 x 的數。
• MIN x y：查詢區間 [x, y] 最小值。

輸出每個 MIN 查詢的答案。

解法：Splay 樹 + 懶標記 + 內存池

用 Splay 維護序列，中序遍歷即為當前順序。每個節點存儲：

• key：節點值
• minv：子樹最小值
• sz：子樹大小
• rev：翻轉標記
• add：區間加標記

關鍵操作實現：

1. 區間提取：將 [l, r] 對應的子樹 Splay 到根的右孩子的左孩子（即 Key_Value），便於整體打標記。
2. 翻轉：交換左右孩子，翻轉標記 ^=1。
3. 區間加：key += d, minv += d, add += d。
4. 循環移位：將區間分為 [l, c-1] 和 [c, r]（c = r - T%len + 1），先切出 [c, r]，再插入到 l-1 後。
5. 插入/刪除：同樣利用 Key_Value 位置掛接/卸載子樹。
6. 查詢最小值：提取區間後直接讀 minv。

核心代碼框架

struct Node { int ch[2], pre, sz; int key, minv; bool rev; int add; } t[MAXN];
int root, tot;

// 懶標記下推
void push_down(int x) {
    if (t[x].rev) { swap(t[x].ch[0], t[x].ch[1]); 
        if (t[x].ch[0]) t[t[x].ch[0]].rev ^= 1;
        if (t[x].ch[1]) t[t[x].ch[1]].rev ^= 1;
        t[x].rev = 0;
    }
    if (t[x].add) {
        for (int d = 0; d < 2; ++d) if (t[x].ch[d]) {
            int c = t[x].ch[d];
            t[c].key += t[x].add; t[c].minv += t[x].add; t[c].add += t[x].add;
        }
        t[x].add = 0;
    }
}

// 區間操作統一入口：Splay(l, 0); Splay(r, root); 操作 Key_Value
void ADD(int l, int r, int d) { ... }
void REVERSE(int l, int r) { ... }
void REVOLVE(int l, int r, int T) { ... }
void INSERT(int p, int v) { ... }
void DELETE(int p) { ... }
int QUERY_MIN(int l, int r) { ... }

複雜度

所有操作攤還 O(log N)，總時間 O((N+M) log N)，空間 O(N+M)。內存池避免頻繁 new/delete。