stl之rope大法好及可持久化并查集用法

rope大法好

rope是c++的stl库中的一个叫做可持久化平衡树的结构，这个神奇的结构支持什么功能呢？看测试代码：

#include<iostream>
#include<cstdio>
#include<ext/rope>//头文件
using namespace std;
using namespace __gnu_cxx;//使用rope要加这句
#define LL long long
rope<char> tmp;
char test[100]="I am cute.";
int main(){
    int i,j;
    tmp.push_back('h');//在末尾插入一个字符
    cout<<tmp<<endl;
    tmp.insert(1,'e');//在第pos位置上插入一串/个字符
    tmp.insert(2," is gaood");
    cout<<tmp<<endl;
    tmp.erase(7,2);//从第7位开始连续删除两个字符
    cout<<tmp<<endl;
    tmp.copy(6,2,test);//将从第6位开始的两个字符插入到test开头
    cout<<tmp<<"           "<<test<<endl;
    tmp.replace(1,'i');tmp.replace(0,"bosh");//修改pos位置上的字符为...
    cout<<tmp<<endl;
    cout<<tmp.substr(0,5)<<endl;//从第0位开始提取5个字符
    cout<<tmp.substr(9)<<endl;//提取第9个字符（默认提取一个）
    cout<<tmp.at(3)<<endl;//访问第3个字符
    return 0;
}

测试结果：

h
he is gaood
he is god
he is god           goam cute.
boshi is god
boshi
g
h

《OI·创世纪》为了报复boshi大佬而重新修订版（现已删除）

rope的可持久化

那么rope怎么实现可持久化？？？
很简单，建一堆rope即可。有时候也是通过转化指针来实现更快地查询历史版本的。总之rope实现历史版本很快的
那让我们愉快地做一道模板题吧：
Uva12538
支持三种操作：
1.在pos位置插入一串字符
2.从pos位置开始删除长度为l的字符串
3.查询第v个历史版本中从pos位置开始的长度为l的字符串（此操作没有产生新的历史版本）
然后询问进行了加密：pos,l,v均需要减去d，d的定义：所有询问中输出的字符‘c’的数量和。

#include<iostream>
#include<cstdio>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define LL long long
rope<char> tmp,his[50005],kl;
char ch[205];
int n,d,cn;
int main(){
    int i,bj,x,y,v;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d",&bj);
        if(bj==1){
            scanf("%d%s",&x,ch);
            x-=d;tmp.insert(x,ch);//插入
            his[++cn]=tmp;
        }
        else if(bj==2){
            scanf("%d%d",&x,&y);
            x-=d,y-=d;tmp.erase(x-1,y);//删除
            his[++cn]=tmp;
        }
        else {
            scanf("%d%d%d",&v,&x,&y);
            v-=d,x-=d,y-=d;
            kl=his[v].substr(x-1,y);//提取
            d+=count(kl.begin(),kl.end(),'c');
            cout<<kl<<endl;
        }
    }
    return 0;
}

可持久化并查集

瞎哔哔了这么多，我到底要说什么呢？——就是可持久化并查集！！！
因为你想，并查集是那么优美而精简的数据结构，达成可持久化就要用麻烦的可持久化线段树/平衡树维护，然而可持久化线段树，即主席树是可以打的很短的，本蒟蒻就打过很短的，但是现在本蒟蒻已经废了，打不出主席树了…是不是非常地令人不爽？还好有rope！！！
例题：暴力一点！直接上bzoj3674
事实上将父亲可持久化就可以了，具体看代码吧，实现还挺简单的….但是——直接暴力rope容易 被查水表 MLE或者RE…
那怎么办呢？其实很简单，如果当前版本没有发生修改，没有必要整体替换一个新版本。我们先开一个数组id表示每一个询问所使用的坂本版本，只有当发生修改时才需要一个新版本。这样空间节省了一半，可以AC！！！
不过慢的死就是了

#include<iostream>
#include<cstdio>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define LL long long
int n,m,ans;
const int N=200005;
rope<int> *f[N];
int a[N],id[N];//id:每一次查询所使用的版本
int find(int t,int x){
    if(f[t]->at(x)==x)return x;
    f[t]->replace(x,find(t,f[t]->at(x)));
    return f[t]->at(x);
}
int main(){
    int i,bj,x,y,r1,r2,t=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)a[i]=i;
    f[0]=new rope<int>(a,a+1+n);
    for(i=1;i<=m;++i){
        scanf("%d",&bj);
        if(bj==1){
            scanf("%d%d",&x,&y);
            x^=ans,y^=ans;
            r1=find(t,x),r2=find(t,y);
            if(r1!=r2){//需要修改，开新版本
                f[i]=new rope<int>(*f[t]);
                f[i]->replace(r1,r2),t=i;
            }
        }
        else if(bj==2){scanf("%d",&x),t=id[x^ans];}//直接更改t
        else {
            scanf("%d%d",&x,&y);
            if(find(t,x^ans)==find(t,y^ans))ans=1;
            else ans=0;
            printf("%d\n",ans);
        }
        id[i]=t;//更新这一次询问后使用的版本
    }
    return 0;
}