[黑科技]__gnu_cxx::rope STL中的可持久化数组

简介

rope是一种可持久化数组，采用块状链表实现，一次操作时间复杂度基本为 O(n√)

引用库

#include<ext/rope> 
using namespace __gnu_cxx;
rope<char>a;

使用方法

基本操作运算符：

支持+,=,[]。

函数

• a.substr(pos,x) 返回一个rope类型，而且等于a[pos~(pos+x-1)]，且两者互不相干。
• a.erase(pos,x) 删除a[pos~(pos+x-1)]，并且把两端拼至一起。
• a.at(x) 返回a[x].
• a.insert(pos,char) 在pos位置插入一个字符或者字符数组(int 也可以)。
• a.replace(pos,x,char) 把a[pos~(pos+x-1)]替换为char。
  rope不支持翻转操作，但可以建两个rope同时维护。

黑科技

rope实现 O(1) 拷贝历史版本

rope<char>*a,*b;
a=new rope<char>;
b=new rope<char>(*a);

应用:

BZOJ1269

#include<bits/stdc++.h>
#include<ext/rope> 
using namespace std;
using namespace __gnu_cxx;
const int Maxn=1024*1024*2+50;
int n,len=0,pos;
rope<char>a,b,tmp;
char ch[Maxn];
int main(){
    scanf("%d",&n);
    while(n--){
        static char op[10];
        scanf("%s",op+1);
        switch(op[1]){
            case 'M':{scanf("%d",&pos);break;}
            case 'I':{
                int l;scanf("%d",&l);int p2=len-pos;
                for(int i=1;i<=l;i++){
                    ch[i]=getchar();
                    while(ch[i]=='\n')ch[i]=getchar();
                }
                ch[l+1]=0;
                a.insert(pos,ch+1);
                reverse(ch+1,ch+l+1);
                b.insert(p2,ch+1);
                len+=l;
                break;  
            }
            case 'D':{
                int l;scanf("%d",&l);
                a.erase(pos,l);
                b.erase(len-pos-l,l);
                len-=l; 
                break;
            }
            case 'R':{
                int l;scanf("%d",&l);
                tmp=a.substr(pos,l);
                a=a.substr(0,pos)+b.substr(len-pos-l,l)+a.substr(pos+l,len-pos-l);
                b=b.substr(0,len-pos-l)+tmp+b.substr(len-pos,pos);
                break;
            }
            case 'G':{putchar(a[pos]);putchar('\n');break;}
            case 'P':{--pos;break;}
            case 'N':{++pos;break;}
            default:break;
        }
    }
}