前景

可持久化数组在许多地方有广泛的应用:可持久化并查集、支持回退操作的字符串、可持久化数据结构。

准备工作

我们需要对应的头文件和命名空间,这都是标准c++支持的。

#include <ext/rope>
using namespace __gnu_cxx;

rope的原理与基本操作

rope是给予维护深度平衡的可持久化平衡树。每次操作都会新建节点,因此内部是可持久化的。
rope一般用来维护一个支持历史版本查询的字符串。它本身也可以像字符串一样使用。

#include <ext/rope>
using namespace __gnu_cxx;
rope<char> str,x;
str.insert(pos,"abc")//在pos位置开始插入"abc"
str.push_back("x")//在末尾追加"x"
str.erase(a,b)//在a位置开始删除b个
str.replace(a,"abc")//在a位置开始用"abc"替换
str.substr(a,b)//返回从a位置开始共b个的字符串
str.reverse(a,b)//反转[a,b)区间,虽然很慢

rope的可持久化

一般,我们可以利用rope底层可持久化的机制,进行O(1)回退。也就是我们只需要回退根节点的版本,我们就可以很顺利地访问当时的所有节点了。故回退复杂度为O(1)
可持久化rope的初始化:

rope<char>*ver[100];
ver[0]=new rope<char>();

可持久化rope建立新版本和回退旧版本:

ver[i]=new rope<char>(*ver[i-1]);//从版本(i-1)建立新版本i
ver[i]=ver[i-1]//版本i回退为版本(i-1)

一道模板题(Version Controlled IDE-UVa12538)

给定一个字符串,要求支持以下操作:
1 a str 在a位置插入str
2 a b 删除a到b的字符串
3 a b c 输出a版本的b开始的c个字符
输入已经进行加密,请将每个数据的数字减去你已经输出的’c’的个数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ext/rope>

#define MX 1000001

using namespace std;
using namespace __gnu_cxx;

char str[MX];
rope<char> *rp[50001],tmp;
int ver[MX],num,n,d;

int main()
{
    rp[0]=new rope<char>();
    int op,a,b,c;
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        rp[i]=new rope<char>(*rp[i-1]);
        scanf("%d",&op);
        if(op==1)
        {
            ver[++num]=i;
            scanf("%d%s",&a,str);
            rp[i]->insert(a-d,str);
        }
        else if(op==2)
        {
            ver[++num]=i;
            scanf("%d%d",&a,&b);
            rp[i]->erase(a-1-d,b-d);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            tmp=(rp[ver[a-d]]->substr(b-1-d,c-d));
            d+=count(tmp.begin(), tmp.end(), 'c');
            cout<<tmp<<endl;
        }
    }
    return 0;
}

又是一道模板题(可持久化并查集-BZOJ3673)

n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0

0<n,m<=2*10^4

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ext/rope>

#define MX 20002

using namespace std;
using namespace __gnu_cxx;

rope<int> *fa[MX];
int src[MX];
int n,m;

int findfa(int x,int ver)
{
    if(fa[ver]->at(x)==x)return x;
    else
    {
        fa[ver]->replace(x,findfa(fa[ver]->at(x),ver));
        return fa[ver]->at(x);
    }
}

void comb(int a,int b,int ver)
{
    int f1,f2;
    f1=findfa(a,ver);
    f2=findfa(b,ver);
    fa[ver]->replace(f1,f2);
}

int same(int a,int b,int ver)
{
    int f1,f2;
    f1=findfa(a,ver);
    f2=findfa(b,ver);
    return (f1==f2);
}

int main()
{
    int a,b,o;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)src[i]=i;
    fa[0]=new rope<int>(src,src+n+1);
    for(int i=1;i<=m;i++)
    {
        fa[i]=new rope<int>(*fa[i-1]);
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d%d",&a,&b);
            comb(a,b,i);
        }
        else if(o==2)
        {
            scanf("%d",&a);
            fa[i]=fa[a];
        }
        else
        {
            scanf("%d%d",&a,&b);
            cout<<same(a,b,i)<<endl;
        }
    }
    return 0;
}
分类: 文章

1 条评论

konnyakuxzy · 2018年3月4日 1:13 上午

Orz Boshi
在boshi学完rope的一千年后的这个半夜蒟蒻XZY也学了rope
然后发现一个奇怪的东西
就是您那个可持久化并查集里的那个findfa函数,最好写成这种形式:

int findfa(int x,int ver)
{
    if(fa[ver]->at(x)==x)return x;
    else
    {
        int tmp = findfa(fa[ver]->at(x),ver);
        if (tmp == fa[ver]->at(x)) return tmp;
        fa[ver]->replace(x, tmp);
        return tmp;
    }
}

究其原因是如果您直接就replace的话会导致空间的增加。
很多时候我们路径并没有被压缩,但是被访问了,这时候就没有必要replace浪费没用的空间。
比如您可以测测BZOJ – 3674那题,是此题的数据加强版
若不修改的话会爆空间QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *