BZOJ 1269：文本編輯器——Splay 树实现序列操作

題目描述

實現文本編輯器核心操作：移動光標、插入、刪除、反轉區間、查詢字符。操作數 ≤ 10⁵，總長度 ≤ 2×10⁶。

Splay 树維護序列

• 每個節點存一個字符，子樹大小 sz
• 翻轉標記 rev 下推交換左右子樹
• 虛擬頭尾節點 # 和 ! 簡化邊界
• 關鍵操作：rotate、splay、build（建平衡子樹）、split/merge 隱含在旋轉到位置中

核心操作實現

// 旋轉到第 k 位（0-based）在根，第 k+1 位在根右子
void rotate_to(int k, Node* goal) { ... }

// 插入長度 len 的字符串
void insert() {
    rotate_to(pos, null);
    rotate_to(pos+1, root);
    build(L(R(root)), R(root), 0, len-1);
    push_up(R(root)); push_up(root);
}

// 刪除 len 個字符
void delete() {
    rotate_to(pos, null);
    rotate_to(pos+len+1, root);
    recycle(L(R(root))); L(R(root)) = null;
    push_up(R(root)); push_up(root);
}

// 反轉 [pos, pos+len-1]
void reverse() {
    rotate_to(pos, null);
    rotate_to(pos+len+1, root);
    L(R(root))->rev ^= 1;
}

// 查詢光標位置字符
char query() {
    rotate_to(pos+1, null);
    return root->val;
}

節點回收優化

用棧 st[] 回收刪除節點，新建節點優先複用，避免頻繁 new/delete。

複雜度

• 單次操作：均攤 O(log n)
• 總時間：O((n+q) log n)