POJ 3580 SuperMemo：Splay 树區間加法、翻轉、旋轉、插入、刪除、查最小值綜合模板

問題描述

維護一個序列（初始長度 n ≤ 100,000），支持 6 種操作（m ≤ 100,000）：

• 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 節點結構與懶標記

struct Node {
    int ch[2], fa, sz;
    int val, mn;      // 值、子樹最小值
    int add_tag;      // 區間加法標記
    bool rev_tag;     // 翻轉標記
} t[MAXN]; // MAXN = 200005 (初始 n + 插入 m)

#define key t[t[rt].ch[1]].ch[0] // 當前操作區間根

核心懶標記下推

void push_add(int x, int v) {
    if (!x) return;
    t[x].add_tag += v;
    t[x].mn += v;
    t[x].val += v;
}

void push_rev(int x) {
    if (!x) return;
    t[x].rev_tag ^= 1;
    swap(t[x].ch[0], t[x].ch[1]);
}

void pushdown(int x) {
    if (!x) return;
    if (t[x].add_tag) {
        push_add(t[x].ch[0], t[x].add_tag);
        push_add(t[x].ch[1], t[x].add_tag);
        t[x].add_tag = 0;
    }
    if (t[x].rev_tag) {
        push_rev(t[x].ch[0]);
        push_rev(t[x].ch[1]);
        t[x].rev_tag = 0;
    }
}

區間分離統一入口

// 將區間 [l, r] 旋伸至 key 位置
void split(int l, int r) {
    int x = find(rt, l-1); // 第 l-1 個節點（左哨兵）
    int y = find(rt, r+1); // 第 r+1 個節點（右哨兵）
    splay(x, rt);
    splay(y, t[rt].ch[1]);
    // 現在 key = t[t[rt].ch[1]].ch[0] 即為 [l, r] 區間根
}

六大操作實現

初始化與建樹

// 雙哨兵：-INF 和 +INF，值不參與最小值計算
newnode(rt, INF, 0);
newnode(t[rt].ch[1], INF, rt);
pushup(t[rt].ch[1]); pushup(rt);

build(key, 1, n, t[rt].ch[1]); // 遞歸構建平衡樹
pushup(t[rt].ch[1]); pushup(rt);

關鍵細節避坑

• 旋轉操作：T = (T % len + len) % len 處理負數；T==0 直接返回
• 懶標記順序：pushdown 中先處理 add 再處理 rev，或根據具體語義調整
• 輸入讀取：大數據量用自寫 read() 快速讀整數，scanf("%s", op) 讀操作碼
• 多測試用例：while (scanf("%d", &n) != EOF) 循環，每輪重置所有全局變量

複雜度

• 單次操作均攤 O(log N)
• 總時間 O((n+m) log N) ≪ 5s 時限
• 空間 O(n+m) ≤ 200,000 節點

總結

本題是 Splay 树區間維護的「六邊形戰士」模板題：加法、翻轉、旋轉、插入、刪除、查最值全覆蓋。掌握 split 統一區間暴露、雙哨兵簡化邊界、多標記共存下推順序、旋轉操作的「剪切-粘貼」邏輯，即可舉一反三解決動態序列區間操作大類問題。