[rope大法好] STL里面的可持久化平衡树--rope

简单用法：

#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)     // 在末尾添加x

x->insert(pos,x)    // 在pos插入x

x->erase(pos,x)     // 从pos开始删除x个

x->replace(pos,x)   // 从pos开始换成x

x->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

巴特西

[rope大法好] STL里面的可持久化平衡树--rope

最新文章

热门文章