UVa12538 - Version Controlled IDE (Rope)

題目大意：

我們需要版本控制一份文件，類型如下：
type 1 ，插入字串在 p 位置
type 2 ，移除字串從 p 位置開始移除 c 個字元
type 3 ，查詢 v 版本從 p 位置開始輸出 c 個字元
每進行一次 type 1 or 2 的動作，就增加一版本。
我們順便進行加密混淆的動作，每一次只要 type 3 輸出的字元中擁有 ‘c’，則接下來 除了 type 以外的數字都會因為前面 type 3 輸出字元中有多少的 c，則會增加多少數字。

分析：

通常大家看到這題直覺都會是用 string 來寫這題吧！但這題不是 QAQ。
這題要用 string 的另外一個好朋友 rope 來解決，rope 的結構為「可持久化平衡樹」，他在加入資料時不破壞舊有狀態，這樣使得每次在插入新增時效率來比 string 更優秀。

下圖為 wiki string 與 rope 的複雜度比較圖

在這需要大量插入移除的題目中，rope 是再好不過的了！且他語法也跟 string 大同小異，上手起來也不至於太久。

小提醒:

type 2 and type 3 的 p 都是從 1 開始，所以必須要 -1，因為電腦從 0 開始呀！

rope.insert()，裡面放的是字元陣列！所以如果是 string，需要變成 string.c_str()，才有辦法讀進去喔！

心得

查了下 string 中文是細繩，rope 是粗繩，嗯? 怎麼感覺好像特斯拉與愛迪生的感覺呢wwww，主流都是 string 沒有 rope 阿 ಥ⌣ಥ。不過被我學了一課，嗯! 我又多學了一些知識，開心。

參考連結

rope大法好
c++ rope 基本應用
Rope (data structure)

#include <iostream>
#include <bits/stdc++.h>
#include <ext/rope>
#define LOCAL
#define MAXN 50020
using namespace std;
using namespace __gnu_cxx ;

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int n , t , a , b , c , d=0 ;
    int v = 0 ;
    string strA ;
    rope<char> r[MAXN] , rtmp ;
    cin >> n ;
    while(n--){
        cin >> t ;

        if(t==1){
            cin >> a ;
            cin >> strA ;
            a -= d ;
            r[++v] = r[v] ;
            r[v].insert(a,strA.c_str());
            //debug
            //cout << r[v] << '\n' ;
        }
        else if(t==2){
            cin >> a >> b ;
            a -= d ; b -= d ;
            r[++v] = r[v] ;
            r[v].erase(a-1,b);
            //debug
            //cout << r[v] << ' ' << r[v-1] << '\n' ;
        }
        else if(t==3){
            cin >> a >> b >> c ;
            a -= d ; b -= d ; c -= d ;
            rtmp = r[a].substr(b-1,c) ;
            cout << rtmp << '\n' ;
            d += count(rtmp.begin() , rtmp.end() , 'c' );
        }
    }
    return 0;
}