简单用法：

#include <ext/rope>using namespace __gnu_cxx;int a[1000];rope<int> x;rope<int> x(a,a + n);rope<int> a(x);x->at(10);x[10];x->push_back(x)     // 在末尾添加xx->insert(pos,x)    // 在pos插入xx->erase(pos,x)     // 从pos开始删除x个x->replace(pos,x)   // 从pos开始换成xx->substr(pos,x)    // 提取pos开始x个

例题一：

IOI2012

scrivener

题意

设计支持如下 3 种操作：
1.T x：在文章末尾打下一个小写字母 x。(type 操作) 
2.U x：撤销最后的x 次修改操作。（Undo 操作）
（注意Query 操作并不算修改操作）
3.Q x：询问当前文章中第x 个字母并输出。（Query 操作）

操作数n<=100000 在线算法

clj都说这是道rope傻逼题……

#include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>#include<ext/rope>using namespace std;using namespace __gnu_cxx;const int maxn=1e5+10;rope<char> *his[maxn];int n;int d[maxn];inline int lowbit(int x){ return x&-x; }inline void updata(int x){ while(x<=n){ d[x]++; x+=lowbit(x); } }inline int get(int x){ int res=0; while(x){ res+=d[x]; x-=lowbit(x); }return res; }inline char getC(){ char ch=getchar(); while(!isalpha(ch))ch=getchar(); return ch; }inline int getint(){    int res=0; char ch,ok=0;    while(ch=getchar())    {        if(isdigit(ch)){ res*=10;res+=ch-‘0‘;ok=1; }        else if(ok)break;    }    return res;}void deb(rope<char> s){    for(int i=0;i<s.length();i++)        cout<<s[i];puts("");}int main(){//    freopen("type.in","r",stdin);//    freopen("type.out","w",stdout);    n=getint();    his[0]=new rope<char>();    for(int i=1;i<=n;i++)    {        his[i]=new rope<char>(*his[i-1]);        // deb(*his[i]);        char opt=getC();        if(opt==‘T‘)        {            char x=getC();            his[i]->push_back(x);            updata(i);        }        else if(opt==‘U‘)        {            updata(i);            int x=getint();            int l=1,r=i,mid,now=get(i);            while(l<r)            {                mid=(l+r)>>1;                if(now-get(mid)>x) l=mid+1;                else r=mid;            }            his[i]=his[l-1];        }        else if(opt==‘Q‘)        {            int x=getint()-1;            putchar(his[i]->at(x));            putchar(‘\n‘);        } // deb(*his[i]);    }    return 0;}

其中，实现可持久化的操作是：his[i]=new rope<char>(*his[i-1]);

他可以实现O(1)的copy历史版本，因为rope的底层是红黑树，所以copy时只需copy根指针。

一键持久化……

例题二：

BZOJ 3673: 可持久化并查集 by zky

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

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

分析：直接可持久化并查集的fa数组就可以了。

ACCode：

#include <cstdio>#include <ext/rope>using namespace std;using namespace __gnu_cxx;const int maxm = 20010;rope<int> *rp[maxm];int find(int i,int x){    if(rp[i]->at(x) == x)   return x;    int f = find(i,rp[i]->at(x));    if(f == rp[i]->at(x))   return f;    rp[i]->replace(x,f);    return rp[i]->at(x);}inline void merge(int i,int x,int y){    x = find(i,x),y = find(i,y);    if(x != y)  rp[i]->replace(y,x);}int a[maxm],lastans;int main(){    int n,m;    scanf("%d%d",&n,&m);    for(int i = 1;i <= n;i ++)  a[i] = i;    rp[0] = new rope<int> (a,a + n + 1);    for(int i = 1;i <= m;i ++)    {        rp[i] = new rope<int> (*rp[i - 1]);        int opt;    scanf("%d",&opt);        if(opt == 1)        {            int a,b;    scanf("%d%d",&a,&b);            merge(i,a/* ^ lastans*/,b/* ^ lastans*/);        }        else if(opt == 2)        {            int k;  scanf("%d",&k);            rp[i] = rp[k/* ^ lastans*/];        }        else        {            int a,b;    scanf("%d%d",&a,&b);            printf("%d\n",lastans = (find(i,a/* ^ lastans*/) == find(i,b/* ^ lastans*/)));        }    }    return 0;}

例题三：

AHOI2006文本编辑器editor

题意

设计数据结构支持

插入删除反转字符串

分析：

由于rope的底层实现，insert，erase，get都是logn的

就是翻转不行，不是自己手写的打不了标记啊！！

怎么办？

答：同时维护一正一反两个rope……反转即交换两个子串……Orz……

区间循环位移？简单，拆成多个子串连起来就好了……

区间a变b b变c c变d …… z变a？ 呃……维护26个rope？

区间和？滚蛋，那是线段树的活

区间kth？sorry，与数值有关的操作rope一概不支持……

5555 维修数列只能自己写了……

ACCode:

#include <cstdio> #include <ext/rope> #include <iostream> #include <algorithm> using namespace std; using namespace __gnu_cxx; crope a,b,tmp; char s[10]; int now,n,len,size; char str[2000000],rstr[2000000]; int main(){     scanf("%d",&n);     while(n--)    {         scanf("%s",s);         switch(s[0])        {             case ‘M‘:            {                scanf("%d",&now);                break;            }             case ‘P‘:            {                now--;                break;            }             case ‘N‘:            {                now++;                break;            }             case ‘G‘:            {                putchar(a[now]);                putchar(‘\n‘);                break;            }             case ‘I‘:            {                 scanf("%d",&size);                 len=a.length();                 for(int i=0;i<size;i++)                {                     do                    {                        str[i]=getchar();                    }                     while(str[i]==‘\n‘);                     rstr[size-i-1]=str[i];                 }                 rstr[size]=str[size]=‘\0‘;                 a.insert(now,str);                 b.insert(len-now,rstr);                 break;             }                           case ‘D‘:            {                 scanf("%d",&size);                 len=a.length();                 a.erase(now,size);                 b.erase(len-now-size,size);                 break;             }             case ‘R‘:            {                 scanf("%d",&size);                 len=a.length();                 tmp=a.substr(now,size);                 a=a.substr(0,now) + b.substr(len-now-size,size) + a.substr(now+size,len-now-size);                 b=b.substr(0,len-now-size)+tmp+b.substr(len-now,now);                 break;             }         }     }     return 0; }

END