您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 3487 Play with Chain：Splay 树區間剪切、翻轉與插入綜合實戰

編輯：關於C++

問題描述

初始鏈為 1, 2, ..., n（n ≤ 300,000），支持 m 次操作（m ≤ 300,000）：

CUT a b c：剪切區間 [a, b]，插入到第 c 個元素之後（c=0 表示插到頭部）
FLIP a b：區間 [a, b] 翻轉（逆序）

最終輸出鏈中所有元素。多測試用例，以 -1 -1 結束。

Splay 區間操作統一框架

雙哨兵節點（1 和 n+2 位置），中序遍歷即為鏈序列。核心操作 split(l, r) 將區間 [l, r] 旋伸至 key = c[c[rt][1]][0]（根的右子樹的左子樹）。

關鍵數據結構

const int MAXN = 300005;
int ch[MAXN][2], fa[MAXN], sz[MAXN];
bool rev[MAXN]; // 翻轉懶標記
int rt, tot;

// 節點值即為其初始位置（1~n），哨兵為 0 和 n+1
// 建樹：遞歸構建平衡樹，O(n)
void build(int l, int r, int f) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    sz[mid] = 1; fa[mid] = f; sz[mid] = r - l + 1;
    ch[f][mid > f] = mid;
    if (l == r) return;
    build(l, mid-1, mid);
    build(mid+1, r, mid);
}

懶標記下推與翻轉

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

void pushdown(int x) {
    if (!x || !rev[x]) return;
    push_rev(ch[x][0]);
    push_rev(ch[x][1]);
    rev[x] = 0;
}

// Splay 前必須將路徑上所有標記下推
void relax(int x, int goal) {
    if (x != goal) relax(fa[x], goal);
    pushdown(x);
}

CUT 操作實現

void solve_cut(int l, int r, int c) {
    // 1. 分離 [l, r] 區間到 key
    split(l, r);
    int cut_tree = key; key = 0; // 斷開
    pushup(ch[rt][1]); pushup(rt);
    
    // 2. 在剩餘序列中分離插入位置 [c+1, c] (空區間)
    split(c+1, c);
    key = cut_tree; fa[cut_tree] = ch[rt][1]; // 接上
    pushup(ch[rt][1]); pushup(rt);
}

關鍵：split(c+1, c) 產生一個空區間作為插入點，key 指向插入位置的父節點（即 c[rt][1] 的左子樹位置）。

FLIP 操作實現

void solve_flip(int l, int r) {
    split(l, r);
    push_rev(key); // 打翻轉標記
    pushup(ch[rt][1]); pushup(rt);
}

輸入讀取陷阱與對策

題目數據行尾可能有空格，導致 scanf("%s", op) 讀取失敗。解決方案：

char op[10];
while (scanf("%s", op) == 1) {
    if (op[0] == 'C') { // CUT
        int a = read()+1, b = read()+1, c = read()+1;
        solve_cut(a, b, c);
    } else { // FLIP
        int a = read()+1, b = read()+1;
        solve_flip(a, b);
    }
}

用 read() 手寫快速讀整數，scanf("%s") 讀操作碼，避開行尾空格干擾。

最終輸出

void inorder(int x) {
    if (!x) return;
    pushdown(x);
    inorder(ch[x][0]);
    if (x != 1 && x != n+2) { // 跳過哨兵
        if (flag++) printf(" %d", x-1); // 值 = 位置-1
        else printf("%d", x-1);
    }
    inorder(ch[x][1]);
}