首页 > 代码库 > UVALive 6145 Version Controlled IDE（可持久化treap、rope）
UVALive 6145 Version Controlled IDE（可持久化treap、rope）
题目链接：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）：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 struct Node; 5 typedef shared_ptr<Node> Nptr; 6 //typedef Node* Nptr; 7 8 struct Node { 9 Nptr lson, rson; 10 int size, weight; 11 char c; 12 void update() { 13 size = lson->size + rson->size + 1; 14 } 15 }; 16 Nptr nil; 17 18 Nptr new_node(char c) { 19 Nptr x = Nptr(new Node); 20 x->lson = x->rson = nil; 21 x->size = 1; 22 x->weight = rand(); 23 x->c = c; 24 return x; 25 } 26 27 Nptr new_node(char c, Nptr lson, Nptr rson) { 28 Nptr x = Nptr(new Node); 29 x->lson = lson; 30 x->rson = rson; 31 x->update(); 32 x->weight = rand(); 33 x->c = c; 34 return x; 35 } 36 37 void initTreap() { 38 nil = Nptr(new Node); 39 nil->lson = nil->rson = nil; 40 nil->size = 0; 41 } 42 43 Nptr build(char *st, char *ed) { 44 if(st == ed) return nil; 45 assert(st < ed); 46 char *mid = st + (ed - st) / 2; 47 return new_node(*mid, build(st, mid), build(mid + 1, ed)); 48 } 49 50 typedef pair<Nptr, Nptr> Ppp; 51 52 Ppp split(Nptr x, int n) { 53 if(n == 0) return make_pair(nil, x); 54 int ls = x->lson->size; 55 56 if(ls >= n) { 57 Ppp a = split(x->lson, n); 58 return make_pair(a.first, new_node(x->c, a.second, x->rson)); 59 } else { 60 Ppp a = split(x->rson, n - ls - 1); 61 return make_pair(new_node(x->c, x->lson, a.first), a.second); 62 } 63 } 64 65 Nptr merge(Nptr a, Nptr b) { 66 if(a == nil) return b; 67 if(b == nil) return a; 68 if(a->weight < b->weight) { 69 return new_node(a->c, a->lson, merge(a->rson, b)); 70 } else { 71 return new_node(b->c, merge(a, b->lson), b->rson); 72 } 73 } 74 75 int print(Nptr x) { 76 if(x == nil) return 0; 77 int res = (x->c == ‘c‘); 78 res += print(x->lson); 79 putchar(x->c); 80 res += print(x->rson); 81 return res; 82 } 83 84 Nptr insert(Nptr x, int pos, char s[]) { 85 Nptr a = build(s, s + strlen(s)); 86 Ppp p = split(x, pos); 87 return merge(p.first, merge(a, p.second)); 88 } 89 90 Nptr remove(Nptr x, int pos, int len) { 91 Ppp a = split(x, pos); 92 Ppp b = split(a.second, len); 93 return merge(a.first, b.second); 94 } 95 96 int print(Nptr x, int pos, int len) { 97 Ppp a = split(x, pos); 98 Ppp b = split(a.second, len); 99 int res = print(b.first);100 puts("");101 return res;102 }103 104 Nptr rt[50010];105 char s[110];106 int n, d, vnow;107 108 int main() {109 initTreap();110 rt[0] = nil;111 112 scanf("%d", &n);113 while(n--) {114 int v, p, c, op;115 scanf("%d", &op);116 if(op == 1) {117 scanf("%d%s", &p, s);118 p -= d;119 vnow++;120 rt[vnow] = insert(rt[vnow - 1], p, s);121 }122 if(op == 2) {123 scanf("%d%d", &p, &c);124 p -= d, c -= d;125 vnow++;126 rt[vnow] = remove(rt[vnow - 1], p - 1, c);127 }128 if(op == 3) {129 scanf("%d%d%d", &v, &p, &c);130 v -= d, p -= d, c -= d;131 d += print(rt[v], p - 1, c);132 }133 }134 }
代码（rope大法 322MS）：
1 #include <bits/stdc++.h> 2 #include <ext/rope> 3 using namespace std; 4 #define FOR(i, n) for(int i = 0; i < n; ++i) 5 6 const int MAXN = 50010; 7 const int MAXS = 200010; 8 9 __gnu_cxx::crope rt[MAXN], tmp;10 11 char s[MAXS];12 int m, vnow, d;13 14 int main() {15 scanf("%d", &m);16 while(m--) {17 int op, p, v, c;18 scanf("%d", &op);19 if(op == 1) {20 scanf("%d%s", &p, s);21 p -= d;22 rt[vnow + 1] = rt[vnow];23 rt[++vnow].insert(p, s);24 } else if(op == 2) {25 scanf("%d%d", &p, &c);26 p -= d, c -= d;27 rt[vnow + 1] = rt[vnow];28 rt[++vnow].erase(p - 1, c);29 } else if(op == 3) {30 scanf("%d%d%d", &v, &p, &c);31 v -= d, p -= d, c -= d;32 tmp = rt[v].substr(p - 1, c);33 printf("%s\n", tmp.c_str());34 d += count(tmp.begin(), tmp.end(), ‘c‘);35 }36 }37 }
UVALive 6145 Version Controlled IDE（可持久化treap、rope）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。