PowerOJ2546: fork【C++ STL __gnu_cxx::rope】

题目链接

我们可以这样定义一个可持久化数组

rope<int> rp;

push_back(x)：在末尾添加x (x是int)

erase(pos, x): 从pos开始删除x个

at(x)/[x]：访问第x个元素

用以上这些操作可以解决这道题了，但是rope还有其他的操作：

如果将rope用来维护char类型，那么：

rope<char> rp;

push_back(x)：在末尾添加x (x是char)

insert(pos,x)：在pos插入x (x是字符串,x后面加个int参数可以只能x中插入几个)

erase(pos,x): 从pos开始删除x个

replace(pos,x): 从pos开始换成x(x是字符串,x后面加个int参数可以只能x中的前几个)

substr(pos,x)：提取pos开始x个

copy(x)：复制rope中所有内容到x字符串

at(x)/[x]：访问第x个元素

例如：

a[1] = new rope<char>('0');

a[2] = new rope<char>(*a[1]);

a[2]->push_back('1');

a[3] = new rope<char>;
*a[3] = a[2]->substr(0, 2);

a[3]->replace(0, 3, "345");

  如何解决这道问题呢？

  很容易解决删除尾和新增尾的操作，但是如何可持久化呢？也就是O(1)的继承历史状态？

a[++N] = new rope<int>(*a[x]);

  新增一个点，然后继承第x个点的状态。

  需要记录它的历史状态。

  但是遗忘应该如何处理呢？可以是用一个head[x]来维护x点的目前的状态（因为可以将rope看成一个数组）。然后删除的话，可以直接从head[x] + 1删除到尾部。

#include <cstdio>
#include <cstring>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int maxn = 5e5 + 7;
int Q, M, N = 1;
rope<int> *a[maxn];
int head[maxn] = {0};
int main()
{
    a[1] = new rope<int>(0);
    scanf("%d%d", &Q, &M);
    char s[10];
    for(int i=1, x, y; i<=Q; i++)
    {
        scanf("%s", s); scanf("%d", &x);
        if(s[0] == 'l') //learn
        {
            scanf("%d", &y);
            head[x]++;
            a[x]->erase(head[x], a[x]->length() - head[x]);
            a[x]->push_back(y);
        }
        else if(s[0] == 'r' && s[1] == 'o') //rollback
        {
            head[x]--;
        }
        else if(s[0] == 'r' && s[1] == 'e') //relearn
        {
            head[x]++;
        }
        else if(s[0] == 'c')    //check
        {
            printf("%d\n", a[x]->at(head[x]));
        }
        else    //fork
        {
            a[++N] = new rope<int>(*a[x]);
            head[N] = head[x];
        }
    }
    return 0;
}