BZOJ 1269 [AHOI2006] 文本編輯器：Splay 树維護字符序列完整解析

問題描述

實現一個支持 7 種操作的文本編輯器：

• Move k：光標移至第 k 個字符前（0 ≤ k ≤ 當前長度）
• Insert n：在光標後插入 n 個字符（後跟 n 行字符串）
• Delete n：刪除光標後 n 個字符
• Get n：輸出光標後 n 個字符
• Prev：光標左移一位
• Next：光標右移一位
• Rotate n：將光標後 n 個字符循環右移一位

數據範圍：操作數 ≤ 50,000，插入總字符數 ≤ 2M，Get 操作 ≤ 20,000。要求高效支持區間操作。

Splay 树區間維護核心思想

將文本序列映射為 Splay 树的中序遍歷序列，每個節點存儲一個字符。通過 雙哨兵節點（頭尾虛擬節點）統一邊界處理。核心操作統一為：

1. Split(l, r)：將區間 [l, r] 旋伸至根的右子樹的左子樹（即 key = c[c[rt][1]][0]）
2. 對 key 所在子樹施加操作（打標記、修改指針等）
3. PushUp 維護子樹大小等信息

關鍵數據結構與操作

// 節點結構
struct Node {
    int ch[2], fa, size;
    char val;
    bool rev; // 翻轉標記
} t[MAXN];

// 核心操作：旋轉、Splay、查找第 k 個、區間分離
void rotate(int x, int &k) { ... }
void splay(int x, int &k) { ... }
int find(int k, int rank) { ... } // 查找第 rank 個節點
void split(int l, int r) { // 將 [l, r] 區間暴露在 key 位置
    int x = find(rt, l-1), y = find(rt, r+1);
    splay(x, rt); splay(y, c[rt][1]);
}

七種操作的 Splay 實現映射

輸入讀取優化避坑指南

題目數據包含可見字符及空格，行尾無空格。關鍵點：

• 讀 N 時用 scanf("%d%*c", &n) 跳過換行符（%*c 讀取不賦值）
• Insert 後的字符串用 fgets 或逐字符 getchar() 讀取保留空格
• 操作命令用 scanf("%s", op) 讀取首單詞判斷類型

複雜度與性能

• 單次操作均攤 O(log N)
• 總時間 O((N+Q) log N) 滿足 10s 時限
• 空間 O(總字符數) ≤ 2M 節點

總結

本題是 Splay 树維護區間操作的經典模板題。關鍵在於：雙哨兵簡化邊界、split 統一區間暴露、懶標記處理翻轉、構建平衡樹初始化。掌握此模式可解決動態序列區間查詢/修改大類問題。