BZOJ 1507 編輯器：利用 STL rope 高效實現文本編輯操作

題目背景

BZOJ 1507 Editor 是一道經典的數據結構題目，源自 NOI 2003。題目要求實現一個支持插入、刪除、移動光標、獲取子串等操作的文本編輯器。數據範圍較大：MOVE 操作不超過 50,000 次，INSERT 和 DELETE 總數不超過 4,000，PREV 和 NEXT 總數不超過 200,000，總插入字符數不超過 2MB，輸出不超過 3MB。若使用普通數組或鏈表模擬，極易超時。

核心思路：GNU ext/rope

C++ 標準庫並未提供原生的可變長度字符串容器，但 GCC 擴展庫 <ext/rope> 提供了 __gnu_cxx::rope（或 crope），它是一種基於平衡樹（如 Splay Tree 或 Treap）實現的持久化字符串結構，支持對數級別的插入、刪除、子串查詢以及隨機訪問，完美契合本題需求。

關鍵操作映射

• Move k：直接將光標位置 pos 設為 k。
• Insert k [string]：讀取 k 個可見字符（ASCII 32~126，忽略換行），調用 txt.insert(pos, str)。
• Delete k：調用 txt.erase(pos, k) 刪除光標後 k 個字符。
• Get k：調用 txt.substr(pos, k) 獲取子串並輸出。
• Prev / Next：光標 pos-- 或 pos++。

參考代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

const int MAXN = 1024 * 1024 * 2 + 10;
crope txt;
char op[10], str[MAXN];
int pos = 0;

int main() {
    int T, x, y, z;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", op);
        if (op[0] == 'M') {          // Move
            scanf("%d", &pos);
        } else if (op[0] == 'I') {   // Insert
            scanf("%d", &x);
            y = 0;
            while (x) {
                char c = getchar();
                if (c >= 32 && c <= 126) {
                    str[y++] = c;
                    x--;
                }
            }
            str[y] = 0;
            txt.insert(pos, str);
        } else if (op[0] == 'D') {   // Delete
            scanf("%d", &x);
            txt.erase(pos, x);
        } else if (op[0] == 'G') {   // Get
            scanf("%d", &x);
            puts(txt.substr(pos, x).c_str());
        } else if (op[0] == 'P') {   // Prev
            pos--;
        } else if (op[0] == 'N') {   // Next
            pos++;
        }
    }
    return 0;
}

複雜度分析

rope 的插入、刪除、子串操作均為 O(log n)，總操作數在 25 萬左右，總字符數 2MB，極易在時限（5000MS）與記憶體限制（165888KB）內通過。注意輸入量大，建議使用 scanf/getchar 而非 iostream 以提高速度。

總結

本題展示了 ext/rope 在處理大規模文本編輯操作時的強大威力。掌握這一非標準但實用的容器，能在競賽中快速解決類似「可變字符串維護」問題，避免手寫平衡樹或 Splay Tree 的繁瑣實現。