BZOJ 1014 [JSOI 2008] 火星人 prefix：Splay 維護字符串 Hash + 二分查詢 LCP

問題描述

維護一個字符串，支持三種操作：

• Query(x, y)：求從位置 x 和 y 開始的最長公共前綴長度（LCP）。
• Modify(x, c)：將位置 x 的字符改為 c。
• Insert(x, c)：在位置 x 後插入字符 c。

字符串長度、操作數均 ≤ 10⁵。

核心思路：Splay + 字符串 Hash + 二分

Splay 維護字符串序列，每節點存儲：

• 字符 c
• 子樹大小 size
• 子樹 Hash 值 hash（基數 27，模 2⁶⁴ 自然溢出）

PushUp 合併 Hash：hash = left->hash + (c-'a'+1)*pow[size[left]] + right->hash*pow[size[left]+1]。

LCP 查詢

對長度 len 二分，用 Splay 將區間 [x, x+len-1] 和 [y, y+len-1] 分別旋到根的右子樹左孩子，比較兩節點的 hash 是否相等。

關鍵代碼結構

struct Node {
    char c; int size; ull hash;
    Node *ch[2], *fa;
    void pushup() {
        size = ch[0]->size + ch[1]->size + 1;
        hash = ch[0]->hash + (c-'a'+1)*pow[ch[0]->size] + ch[1]->hash*pow[ch[0]->size+1];
    }
} *null, *root;

// Splay 基礎操作：rotate, splay, kth, build
// Query: 二分長度，splay 取區間 hash 比較
// Modify: splay 到根，修改 c，pushup
// Insert: splay x+1 到根，x+2 到根右子，插入新節點

複雜度

• Splay 單次操作均攤 O(log n)。
• Query 額外二分 O(log n)，總 O(log² n)。
• Modify/Insert O(log n)。

此題是「Splay 維護序列 + Hash 比較」的經典應用，展示了 Splay 在動態字符串問題中的強大威力。