可持久化treap

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 === stl: rope ===
{{{
#include <cstdio>
#include <iostream>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

crope t,tp[50001],tmp; int po;
char s[101];
int sub;
int main(){
    int n; scanf("%d",&n);
    for (int d,p,v,c;n--;)
    {
        scanf("%d",&d);
        if (d==1)
        {
            scanf("%d%s",&p,s);
            p-=sub;
            t.insert(p,s);//在第p个字符前插入s
            tp[++po]=t;
        }
        else if (d==2)
        {
            scanf("%d%d",&p,&c);
            p-=sub,c-=sub;
            t.erase(p-1,c);//删掉p位置开始的c个字符（包括）
            tp[++po]=t;
        }
        else
        {
            scanf("%d%d%d",&v,&p,&c);
            v-=sub,p-=sub,c-=sub;
            tmp=tp[v].substr(p-1,c);//返回p位置开始的c个字符（包括）
            sub+=count(tmp.begin(),tmp.end(),'c');//计算有多少个字符'c'
            cout<<tmp<<endl;
        }
    }
    return 0;
}
//注：上述代码中erase和substr中p的范围都是[1,len]，所以要减1
}}}

stl: rope

#include <cstdio>
#include <iostream>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
crope t,tp[50001],tmp; int po;
char s[101];
int sub;
int main(){
    int n; scanf("%d",&n);
    for (int d,p,v,c;n--;)
    {
        scanf("%d",&d);
        if (d==1)
        {
            scanf("%d%s",&p,s);
            p-=sub;
            t.insert(p,s);//在第p个字符前插入s
            tp[++po]=t;
        }
        else if (d==2)
        {
            scanf("%d%d",&p,&c);
            p-=sub,c-=sub;
            t.erase(p-1,c);//删掉p位置开始的c个字符（包括）
            tp[++po]=t;
        }
        else
        {
            scanf("%d%d%d",&v,&p,&c);
            v-=sub,p-=sub,c-=sub;
            tmp=tp[v].substr(p-1,c);//返回p位置开始的c个字符（包括）
            sub+=count(tmp.begin(),tmp.end(),'c');//计算有多少个字符'c'
            cout<<tmp<<endl;
        }
    }
    return 0;
}
//注：上述代码中erase和substr中p的范围都是[1,len]，所以要减1