UVA 12538 Version Controlled IDE ( 持久化隨機二元搜尋樹 )

UVa Online Judge - Offline
Here are some good resources I read through in order to understand how to implement persistent RBST for this problem.
morris821028.github.io
blog.csdn.net

#include <bits/stdc++.h>
using namespace std;
const int MAXMEM = 5e7;
const int MAXINT = ~( 1 << 31 );
const int MAXN = 5e4 + 4;
const int MAXLEN = 1e6 + 5;

struct rbst_node{
    static rbst_node mem[MAXMEM];
    char c;
    int size;
    rbst_node *lc, *rc;
    rbst_node(): lc(NULL), rc(NULL){}
    rbst_node(char _c): c(_c), size(1), lc(NULL), rc(NULL){}
    rbst_node(rbst_node *t){ c = t->c, size = t->size, lc = t->lc, rc = t->rc; }
    void pull(){
        size = 1;
        if( lc ) size += lc->size;
        if( rc ) size += rc->size;
    }
} rbst_node::mem[MAXMEM], *ptr = rbst_node::mem;
int size(rbst_node *t){ return t ? t->size : 0; }
void split(rbst_node *t, int k, rbst_node *&a, rbst_node *&b){
    if( !t ) a = b = NULL;
    else{
        if( k <= size( t->lc ) ){
            b = new( ptr++ ) rbst_node( t );
            split( t->lc, k, a, b->lc );
            b->pull();
        } else{
            a = new( ptr++ ) rbst_node( t );
            split( t->rc, k - size( t->lc ) - 1, a->rc, b );
            a->pull();
        }
    }
}
int rnd(){
    static int rand_seed = 20160210; // QQ winter vacation's over
    return rand_seed = ( rand_seed * 0xdefaced + 1 ) & MAXINT;
}
rbst_node* merge(rbst_node *a, rbst_node *b){
    if( !a || !b ) return a ? a : b;
    rbst_node *res;
    if( rnd() % ( a->size + b->size ) < a->size ){
        res = new( ptr++ ) rbst_node( a );
        res->rc = merge( res->rc, b );
    } else{
        res = new( ptr++ ) rbst_node( b );
        res->lc = merge( a, res->lc );
    }
    res->pull();
    return res;
}

int d; // the variable that forced it to be online
void print(rbst_node *t){
    if( !t ) return;
    print( t->lc );
    printf("%c", t->c);
    d += ( t->c == 'c' );
    print( t->rc );
}

int n;
char str[MAXLEN];
int rcnt;
rbst_node *root[MAXN];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        rbst_node *tl, *tm, *tr;
        int op, v, p, c; scanf("%d", &op);
        if( op == 1 ){
            root[ ++rcnt ] = root[ rcnt - 1 ];
            scanf("%d%s", &p, str);
            p -= d;
            split( root[ rcnt ], p, tl, tr );
            for(int j = 0; str[j]; ++j)
                tl = merge( tl, new( ptr++ ) rbst_node( str[j] ) );
            root[ rcnt ] = merge( tl, tr );
        } else if( op == 2 ){
            root[ ++rcnt ] = root[ rcnt - 1 ];
            scanf("%d%d", &p, &c);
            p -= d, c -= d;
            split( root[ rcnt ], p - 1, tl, tr );
            split( tr, c, tm, tr );
            root[ rcnt ] = merge( tl, tr );
        } else{
            scanf("%d%d%d", &v, &p, &c);
            v -= d, p -= d, c -= d;
            split( root[ v ], p - 1, tl, tr );
            split( tr, c, tm, tr );
            print( tm ); puts("");
        }
    }
    return 0;
}

As many people know, rope from c++ stl can work as an alternative. Here's link to the reference for rope:
https://www.sgi.com/tech/stl/Rope.html
though some in the network says it is a persistent block - linked list, in the reference I saw this "A character update requires time roughly logarithmic in the length of the string.", so I assume it is implemented upon a persistent BST. It works excellently when it comes to concatenating, inserting, and especially copying substrings. And BTW, it is named rope just to make some contrast with string, a little more heavy but mighty as well. *Note: I don't know why this doesn't work Hatena/uva12538_crope_wa.cpp at master · 1w0/Hatena · GitHub, maybe someday later I will find the reason.

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int MAXN = 5e4 + 4;

int n;
int d;
int vcnt;
rope<char> t, ver[MAXN];
char str[MAXN];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        int op, v, p, c; scanf("%d", &op);
        if( op == 1 ){
            scanf("%d%s", &p, str);
            p -= d;
            t.insert( p, str );
            ver[ ++vcnt ] = t; // ropes work in a persistent manner
        } else if( op == 2 ){
            scanf("%d%d", &p, &c);
            p -= d, c -= d;
            t.erase( p - 1, c );
            ver[ ++vcnt ] = t;
        } else{
            scanf("%d%d%d", &v, &p, &c);
            p -= d, v -= d, c -= d;
            rope<char> ans = ver[ v ].substr( p - 1, c );
            cout << ans << endl;
            d += count( ans.begin(), ans.end(), 'c' ); // iterator exists for rope
        }
    }
    return 0;
}