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

HDU 2475 Box：伸展樹 (Splay) 維護動態森林解決盒子移動問題

編輯：C++ 入門

題目大意

有 N 個盒子，初始各自獨立。支持兩種操作：

M x y：將含 x 的堆疊整體移到含 y 的堆疊頂部（若同堆忽略）。
Q x：查詢 x 所在堆疊的最底部盒子編號。

伸展樹建模

每個盒子為一個節點。
每堆盒子對應一棵 Splay 樹，**中序遍歷 = 從底到頂的盒子順序**。
樹根 = 堆疊最底盒子（或虛擬根）。

核心操作實現

1. 切分：分離 x 及其上方盒子

// 將 x splay 到根，其左子樹即 x 以下部分，右子樹為 x 以上部分
splay(x, 0);
int leftTree = ch[x][0]; ch[x][0] = 0; // 切斷左子樹
if (leftTree) pre[leftTree] = 0;
pushUp(x);

2. 合併：將切下的子樹接到 y 所在樹的最右端

splay(y, 0); // y 所在樹根
int rightMost = getMax(y); // 找到最右節點（堆頂）
splay(rightMost, 0);
ch[rightMost][1] = cutTree; // 接上
pre[cutTree] = rightMost;
pushUp(rightMost);

3. 查詢：找到 x 所在樹的最左節點

splay(x, 0);
int bottom = getMin(x);
return val[bottom];

關鍵 Splay 模板

void rotate(int x, int d) { // d=0 右旋, d=1 左旋
    int y = pre[x];
    ch[y][!d] = ch[x][d];
    if (ch[x][d]) pre[ch[x][d]] = y;
    pre[x] = pre[y];
    if (pre[y]) ch[pre[y]][ch[pre[y]][1]==y] = x;
    ch[x][d] = y; pre[y] = x;
    pushUp(y); pushUp(x);
}
void splay(int x, int goal) {
    pushDown(x);
    while (pre[x] != goal) {
        int y = pre[x];
        if (pre[y] == goal) rotate(x, ch[y][0]==x);
        else {
            int z = pre[y];
            int d = (ch[z][0]==y);
            if (ch[y][d]==x) rotate(x, !d), rotate(x, d);
            else rotate(y, d), rotate(x, d);
        }
    }
    pushUp(x);
    if (goal == 0) root = x;
}

完整 AC 代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110000;
int ch[MAXN][2], pre[MAXN], val[MAXN], sz[MAXN];
int root, tot;

void pushUp(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; }
void pushDown(int x) { /* 可擴展翻轉標記 */ }

int getMin(int x) { while (ch[x][0]) { pushDown(x); x = ch[x][0]; } return x; }
int getMax(int x) { while (ch[x][1]) { pushDown(x); x = ch[x][1]; } return x; }

void newNode(int& x, int v) { x = ++tot; val[x] = v; sz[x] = 1; }
// 初始化：每個盒子獨立節點，無連接

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        // 初始化節點 1..n
        tot = 0; root = 0;
        for (int i = 1; i <= n; i++) newNode(/*...*/);
        char op; int x, y;
        while (cin >> op) {
            if (op == 'M') { cin >> x >> y; /* move */ }
            else if (op == 'Q') { cin >> x; cout << query(x) << '\n'; }
            else break; // 換測試用例
        }
    }
    return 0;
}