__gnu_cxx::rope 的简单操作

· · 题解

通过如下初始化：

#include<ext/rope>
using namespace __gnu_cxx;

可以引用 rope——可持久化块状链表！

它支持 O(\sqrt{n}) 取出子序列、序列连接，O(1) 在序列后添加元素。

优点在于，它自带可持久化，空间复杂度为 O(n\sqrt{n}+C)，C 为插入的总数。

此题中，可以暴力开 10^6 个 rope，直接通过：

#include<cstdio>
#include<ext/rope>
using namespace __gnu_cxx; 
const int N=1e6+5;
typedef rope<char> Rp;
Rp rp[N];
char buf[N+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
inline void read(int &x){
    for(c=gc;c<'0'||c>'9';c=gc);
    for(x=0;c>='0'&&c<='9';x=x*10+c-'0',c=gc);
}
inline void read(char &x){while(!isalpha(x=gc));}
int q,now,x;
int main(){
    read(q);
    while(q--){
        read(c);
        if(c=='P'){read(x);putchar(rp[now][x]),putchar('\n');}
        else {++now;
            if(c=='T'){read(c),rp[now]=rp[now-1],rp[now].append(c);}
            else read(x),rp[now]=rp[now-x-1];
        }
    }return 0;
}