UVA-12538:Version Controlled IDE

Treap 可持久化数据结构 UVA

describtion.pdf17.5kB

使用可持久化的FHQ_Treap，维护各版本，注意一些题目里的细节就好。

#include<ctime>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000000+9;
int lastans;
int n;
struct PAIR{
    int left,right;
    PAIR(int _x=0,int _y=0):left(_x),right(_y){}
};
struct T{
    int ls,rs;
    char val;
    int size;
    int RD;
}tree[MAXN*22];
int rt[MAXN];
int cnt;
char BUF[MAXN];
int Verson;
int New_Node(char val=0){
    int now=++cnt;
    tree[now].val=val;
    tree[now].size=1;
    tree[now].RD=rand();
    return now;
}
int Copy_Node(int x){
    int now=New_Node();
    tree[now]=tree[x];
    return now;
}
void Clean(T &A){
    A.ls=A.rs=A.val=A.size=A.RD=0;
}
void update(int x){
    tree[x].size=tree[tree[x].ls].size+tree[tree[x].rs].size+1;
}
int Build(char *S,int &len){
    static stack<int> sta;
    while(!sta.empty())sta.pop();
    len=strlen(S);
    int from=cnt+1;
    for(int i=0;i<len;i++){
        int now=++cnt;
        tree[now].RD=rand();
        tree[now].val=S[i];
        tree[now].size=1;
    }
    int to=cnt;
    sta.push(0);
    Clean(tree[0]);
    int top;
    for(int i=from;i<=to;i++){
        while(true){
            top=sta.top();
            if(tree[top].RD<=tree[i].RD)
                break;
            update(top);
            sta.pop();
        }
        tree[i].ls=tree[top].rs;
        tree[top].rs=i;
        sta.push(i);
    }
    while(sta.size()>1){
        update(sta.top());
        sta.pop();
    }
    return tree[0].rs;
}
PAIR split(int k,int val){
    PAIR re;
    if(!k)return re;
    int now=Copy_Node(k);
    if(tree[tree[k].ls].size+1<=val){
        re=split(tree[k].rs,val-(tree[tree[k].ls].size+1));
        tree[now].rs=re.left;
        re.left=now;
    }
    else{
        re=split(tree[k].ls,val);
        tree[now].ls=re.right;
        re.right=now;
    }
    update(now);
    return re;
}
int merge(int x,int y){
    if(x==0 || y==0)
        return x+y;
    if(tree[x].RD<tree[y].RD){
        tree[x].rs=merge(tree[x].rs,y);
        update(x);
        return x;
    }
    else{
        tree[y].ls=merge(x,tree[y].ls);
        update(y);
        return y;
    }
}
void insert(int pre,int now,int loc){
    int len;
    int tmp=Build(BUF,len);
    PAIR rt1=split(rt[pre],loc);
    rt[now]=merge(rt1.left,merge(tmp,rt1.right));
}
void del(int pre,int now,int loc,int len){
    PAIR rt1=split(rt[pre],loc-1);
    PAIR rt2=split(rt1.right,len);
    rt[now]=merge(rt1.left,rt2.right);
}
void InOrder(int k){
    if(!k)return;
    InOrder(tree[k].ls);
    putchar(tree[k].val);
    if(tree[k].val=='c')lastans++;
    InOrder(tree[k].rs);
}
void OUTPUT(int pre,int loc,int len){
    PAIR rt1=split(rt[pre],loc-1);
    PAIR rt2=split(rt1.right,len);
    InOrder(rt2.left);
    puts("");
    rt[pre]=merge(rt1.left,merge(rt2.left,rt2.right));
}
int main(){
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int opt,loc,len,v;
        scanf("%d",&opt);
        switch(opt){
            case 1:scanf("%d",&loc);scanf("%s",BUF);
                   loc-=lastans;
                   Verson++;
                   insert(Verson-1,Verson,loc);
                   break;
            case 2:
                   scanf("%d%d",&loc,&len);
                   loc-=lastans;len-=lastans;
                   Verson++;
                   del(Verson-1,Verson,loc,len);
                   break;
            default:
                   scanf("%d%d%d",&v,&loc,&len);
                   v-=lastans;loc-=lastans;len-=lastans;
                   OUTPUT(v,loc,len);
        }
    }
    return 0;
}