rope

头文件与命名空间：

#include<ext/rope>
using namespace __gnu_cxx;

大概可以称作可持久化平衡树，因为rope适用于大量、冗长的串操作，而不适合单个字符操作。rope类似块状链表。复杂度为$O\sqrt n$。

基本操作：

1）运算符：rope支持operator += -= + - < ==。

2）输入输出：可以用<<运算符由输入输出流读入或输出。

3）长度/大小：调用length()，size()都可以。

4）插入/添加等：

push_back(x);//在末尾添加x
insert(pos,x);//在pos插入x，自然支持整个char数组的一次插入
erase(pos,x);//从pos开始删除x个
copy(pos,len,x);//从pos开始到pos+len为止用x代替
replace(pos,x);//从pos开始换成x
substr(pos,x);//提取pos开始x个
at(x)/[x];//访问第x个元素

rope<int>r

放在主函数外面会快一点。

hash table

头文件与命名空间：

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;

cc_hash_table是拉链法

gp_hash_table是查探法

gp_hash_table更快，一般用这个。

声明方式：

cc_hash_table<int,bool>h;
gp_hash_table<int,bool>h;

除了当数组用外，还支持clear、find和operator[]。

这个也得放在主函数外面。