UVA12538题解

ncwzdlsd · 2023-01-12 19:13:24 · 题解

STL 大法好！

这道题需要我们维护一种数据结构，可以完成 3 种神奇的操作：

1. 插入一个字符串；

2. 删除一个字符串；

3. 查询某个历史版本的字符串。

看到这样的操作，很多大佬可能就要祭出各种平衡树以及可持久化数据结构，但是，还有一种更简便的做法——封装好的 STL。

对于 STL 的 rope，其他题解都有提到，这一篇补充了一些更多的用法，比如配合迭代器，下面是 rope 的详细解释：

rope 是一种神奇的 STL，使用 rope 可以轻松地实现可持久化数据结构。rope 可以在 O(1) 的时间内拷贝历史版本。rope 的本质其实是一种块状链表。

对于 rope 的使用，我们必须加上这两行代码：

#include <ext/rope>
using namespace __gnu_cxx;

一定要加入 using namespace __gnu_cxx; 这一行，之前忘加了导致调了好久。

rope 的定义如下：

rope<char> a,b;//rope<char> is equal to crope
rope<int> s[10005];

rope 的常用操作与 STL 中的其他容器十分类似，具体如下：

rope<int> x;

x.push_back(x);//在末尾加x
x.insert(pos,r);//在pos后加r
x.erase(pos,r);//从pos开始删除r个元素
x.substr(pos,r);//从pos开始拷贝r个元素
x.replace(pos,r);//从pos开始把后面所有元素都替换成r
x.at(r);x[r]//访问x的第r个元素
x.copy(pos,len,r);//从pos开始把后面len个元素替换成r
x.pop_back();
x.delete(r,len);//从第r个元素开始清除len个元素
x.replace(pos,len,r);//从pos开始把后面len个元素替换为r
x.size();//返回长度
x.max_size;//返回最大长度
itb=multable_begin();//指向起点的迭代器
ite=multable_end();//指向终点的迭代器

对于一些常用操作，时间复杂度如下：

• push_back()、pop_back()、delete()、substr()、replace()：O(\log N)；

• insert()：最好 O(\log N)，最坏 O(N)。

然后，一道紫题就成功被我们转化成了一道 rope 使用的模板题！

代码就不放了，要自己写才能熟悉操作哟！