学习一下rope做一下笔记.....
头文件
#include <ext/rope>
文件头
using namespace __gnu_cxx;
变量声明
rope<Type> x;
成员函数
size() O(1)放心用.
push_back(v) 不解释
push_front(v) .....
insert(p,v) 在位置p插入元素v. 插入后使用x[v]调用. 也就是说insert(0,v)表示在队头插入v,也就是push_front(v).
insert(p,s,v) 在位置p插入s个元素v.插入的第一个元素的下标是p,原来在位置p的元素现在在位置p+s.
append(s,v) 在末尾增加s个元素v. 简直是没用的函数....
erase(p) 删除位置p后面(包括位置p)所有的元素. 果断被坑了一发.
erase(p,s) 从位置p开始(包括位置p)删除s个元素.
operator[k] 取值....
由于使用平衡树实现,多数函数都是 $O(\log{n})$ 或者 $O(s\log{n})$ 的.
呃,简单的操作还是尽量不要用insert,多用push和append,不然比较慢=.=....
接下来是rope特色...
rope<Type>(t) 呃....构造函数.t是另一个rope.时间复杂度是 $O(1)$ 的!!!!
1 rope<int>*x=new rope<int>;
2 rope<int>*t;
3 for(int i=0;i<100000;i++)
4 {
5 x->append(10,1);
6 t=new rope<int>(*x);
7 } 耗时1203ms.
1 rope<int>*x=new rope<int>;
2 rope<int>*t;
3 for(int i=0;i<100000;i++)
4 {
5 t=new rope<int>(*x);
6 t->append(10,1);
7 } 耗时359ms.
使用方法
0.修改元素的值: 虽然重载了方括号运算符但是赋值是不可以的....用erase+insert....
1.遍历: for(int i=0;i<x.size();i++) {...}; iterator 似乎不能用......
2.可持久化:
t[i]=new rope<int>(*t[i-1]); 对整个树可持久化.
AC BZOJ 3673 可持久化并查集
1 #include <cstdio>
2 #include <fstream>
3 #include <iostream>
4
5 #include <cstdlib>
6 #include <cstring>
7 #include <algorithm>
8 #include <cmath>
9
10 #include <queue>
11 #include <vector>
12 #include <map>
13 #include <set>
14 #include <stack>
15 #include <list>
16
17 typedef unsigned int uint;
18 typedef long long int ll;
19 typedef unsigned long long int ull;
20 typedef double db;
21 typedef long double ldb;
22
23 using namespace std;
24
25 inline int getint()
26 {
27 int res=0;
28 char c=getchar();
29 bool mi=false;
30 while((c<'0' || c>'9')/* && !feof(stdin)*/) mi=(c=='-'),c=getchar();
31 while('0'<=c && c<='9'/* && !feof(stdin)*/) res=res*10+c-'0',c=getchar();
32 return mi ? -res : res;
33 }
34 inline ll getll()
35 {
36 ll res=0;
37 char c=getchar();
38 bool mi=false;
39 while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
40 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
41 return mi ? -res : res;
42 }
43
44 //==============================================================================
45 //==============================================================================
46 //==============================================================================
47 //==============================================================================
48
49 #include <ext/rope>
50 using namespace __gnu_cxx;
51
52 int n,m;
53
54 typedef rope<int> rp;
55 rp*t[400050];
56
57 void change(int x,int v,rp&F)
58 { F.erase(x,1); F.insert(x,v); }
59
60 int findf(int x,rp&F)
61 { while(F[x]!=x) x=F[x]; return x; }
62
63 void connect(int a,int b,rp&F)
64 { change(findf(a,F),findf(b,F),F); }
65
66 int main()
67 {
68 n=getint();
69 m=getint();
70
71 t[0]=new rp;
72 for(int i=0;i<n;i++) t[0]->push_back(i);
73
74 for(int i=1;i<=m;i++)
75 {
76 int c=getint();
77 if(c==1)
78 {
79 int a=getint()-1;
80 int b=getint()-1;
81 t[i]=new rp(*t[i-1]);
82 if(findf(a,*t[i])!=findf(b,*t[i])) connect(a,b,*t[i]);
83 }
84 else if(c==2)
85 {
86 t[i]=t[getint()];
87 }
88 else if(c==3)
89 {
90 t[i]=t[i-1];
91 int a=getint()-1;
92 int b=getint()-1;
93 printf("%d\n",findf(a,*t[i])==findf(b,*t[i]));
94 }
95 }
96
97 return 0;
98 } 加强版居然不是TLE而是MLE.....
(可持久化)平衡树还是比不上(可持久化)线段树.....不管在空间上还是时间上....
....