(UVA) 12538 - Version Controlled IDE [可持久化treap]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=441&problem=3983

Persistent Treap !!!

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAX_N = 1e5 + 6;
const int MAX_M = 1e6 + 6;
const int MAX_P = 3e7;

int myRnd() {
    return 10000*(rand()%10000) + (rand()%10000);
}

struct Treap {
    static Treap mem[MAX_P];
    Treap *lc,*rc;
    char c;
    int sz;
    Treap(){}
    Treap(char _c) : lc(NULL),rc(NULL),sz(1),c(_c){}
} Treap::mem[MAX_P], *ptr=Treap::mem ;

int Sz(Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    if (!t) return;
    t->sz = Sz(t->lc) + Sz(t->rc) + 1;
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    Treap* ret;
    if (myRnd() % (Sz(a) + Sz(b)) < Sz(a)) {
        ret = new (ptr++) Treap(*a);
        ret->rc = merge(a->rc,b);
    }
    else {
        ret = new(ptr++) Treap(*b);
        ret->lc=merge(a,b->lc);
    }
    pull(ret);
    return ret;
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (Sz(t->lc) + 1 <= k) {
        a = new(ptr++) Treap(*t);
        split(t->rc,k-Sz(t->lc)-1,a->rc,b);
        pull(a);
    }
    else {
        b=new(ptr++) Treap(*t);
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

int d;
char buf[MAX_M];
Treap* ver[MAX_N];

void print(Treap* t) {
    if (!t) return;
    print(t->lc);
    if (t->c == 'c') d++;
    printf("%c",t->c);
    print(t->rc);
    return;
}

int main () {
    srand(time(NULL));
    int n;
    while (scanf("%d",&n) != EOF) {
        ptr = Treap::mem;
        d=0;
        int v_cnt=0;
        ver[0] = NULL;
        for (int i=1;n>=i;i++) {
            Treap *tl,*tmid,*tr;
            int type;
            scanf("%d",&type);
            if (type==1) {
                v_cnt++;
                ver[v_cnt] = ver[v_cnt-1];
                int p;
                scanf("%d %s",&p,buf);
                p-=d;
//                cout<<"p = "<<p<<endl;
                split(ver[v_cnt],p,tl,tr);
                for (int j=0;buf[j];j++) {
//                    cout<<"buf["<<j<<"] = "<<buf[j]<<endl;
                    tl = merge(tl,new(ptr++)Treap(buf[j]));
                }
                ver[v_cnt] = merge(tl,tr);
//                print(ver[v_cnt]);puts("");
            }
            else if (type==2) {
                v_cnt++;
                ver[v_cnt] = ver[v_cnt-1];
                int p,c;
                scanf("%d %d",&p,&c);
                p-=d;
                c-=d;
                split(ver[v_cnt],p-1,tl,tr);
                split(tr,c,tmid,tr);
                ver[v_cnt] = merge(tl,tr);
            }
            else {
                int v,p,c;
                scanf("%d %d %d",&v,&p,&c);
                v-=d,p-=d,c-=d;
                split(ver[v],p-1,tl,tr);
                split(tr,c,tmid,tr);
                print(tmid);
                puts("");
            }
        }
    }
}