题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4156
题目拷贝难度大我就不复制了。
题目大意：维护一个字符串，要求支持插入、删除操作，还有输出第 i 次操作后的某个子串。强制在线。
思路1：使用可持久化treap可破，详细可见CLJ的《可持久化数据结构的研究》。
思路2：rope大法好，详见：http://blog.csdn.net/guognib/article/details/20563453（文档：http://www.sgi.com/tech/stl/Rope.html），代码短速度快，可惜不能打lazy标记。
PS：自从学了函数式编程，发现可持久化什么的都变简单了。
PS：不用智能指针只要845MS。这真是一个大坑。本来我换成普通指针只是想用于调试……
PS：UVALive居然不保存代码！于是我又去vjudge交了一次。
代码（C++11 2116MS）：
#include <bits/stdc++.h>
using namespace std; struct Node;
typedef shared_ptr<Node> Nptr;
//typedef Node* Nptr; struct Node {
Nptr lson, rson;
int size, weight;
char c;
void update() {
size = lson->size + rson->size + ;
}
};
Nptr nil; Nptr new_node(char c) {
Nptr x = Nptr(new Node);
x->lson = x->rson = nil;
x->size = ;
x->weight = rand();
x->c = c;
return x;
} Nptr new_node(char c, Nptr lson, Nptr rson) {
Nptr x = Nptr(new Node);
x->lson = lson;
x->rson = rson;
x->update();
x->weight = rand();
x->c = c;
return x;
} void initTreap() {
nil = Nptr(new Node);
nil->lson = nil->rson = nil;
nil->size = ;
} Nptr build(char *st, char *ed) {
if(st == ed) return nil;
assert(st < ed);
char *mid = st + (ed - st) / ;
return new_node(*mid, build(st, mid), build(mid + , ed));
} typedef pair<Nptr, Nptr> Ppp; Ppp split(Nptr x, int n) {
if(n == ) return make_pair(nil, x);
int ls = x->lson->size; if(ls >= n) {
Ppp a = split(x->lson, n);
return make_pair(a.first, new_node(x->c, a.second, x->rson));
} else {
Ppp a = split(x->rson, n - ls - );
return make_pair(new_node(x->c, x->lson, a.first), a.second);
}
} Nptr merge(Nptr a, Nptr b) {
if(a == nil) return b;
if(b == nil) return a;
if(a->weight < b->weight) {
return new_node(a->c, a->lson, merge(a->rson, b));
} else {
return new_node(b->c, merge(a, b->lson), b->rson);
}
} int print(Nptr x) {
if(x == nil) return ;
int res = (x->c == 'c');
res += print(x->lson);
putchar(x->c);
res += print(x->rson);
return res;
} Nptr insert(Nptr x, int pos, char s[]) {
Nptr a = build(s, s + strlen(s));
Ppp p = split(x, pos);
return merge(p.first, merge(a, p.second));
} Nptr remove(Nptr x, int pos, int len) {
Ppp a = split(x, pos);
Ppp b = split(a.second, len);
return merge(a.first, b.second);
} int print(Nptr x, int pos, int len) {
Ppp a = split(x, pos);
Ppp b = split(a.second, len);
int res = print(b.first);
puts("");
return res;
} Nptr rt[];
char s[];
int n, d, vnow; int main() {
initTreap();
rt[] = nil; scanf("%d", &n);
while(n--) {
int v, p, c, op;
scanf("%d", &op);
if(op == ) {
scanf("%d%s", &p, s);
p -= d;
vnow++;
rt[vnow] = insert(rt[vnow - ], p, s);
}
if(op == ) {
scanf("%d%d", &p, &c);
p -= d, c -= d;
vnow++;
rt[vnow] = remove(rt[vnow - ], p - , c);
}
if(op == ) {
scanf("%d%d%d", &v, &p, &c);
v -= d, p -= d, c -= d;
d += print(rt[v], p - , c);
}
}
}
代码（rope大法 322MS）：
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
#define FOR(i, n) for(int i = 0; i < n; ++i) const int MAXN = ;
const int MAXS = ; __gnu_cxx::crope rt[MAXN], tmp; char s[MAXS];
int m, vnow, d; int main() {
scanf("%d", &m);
while(m--) {
int op, p, v, c;
scanf("%d", &op);
if(op == ) {
scanf("%d%s", &p, s);
p -= d;
rt[vnow + ] = rt[vnow];
rt[++vnow].insert(p, s);
} else if(op == ) {
scanf("%d%d", &p, &c);
p -= d, c -= d;
rt[vnow + ] = rt[vnow];
rt[++vnow].erase(p - , c);
} else if(op == ) {
scanf("%d%d%d", &v, &p, &c);
v -= d, p -= d, c -= d;
tmp = rt[v].substr(p - , c);
printf("%s\n", tmp.c_str());
d += count(tmp.begin(), tmp.end(), 'c');
}
}
}