Rope 真的是一个非常好用的东西,在非常多的平衡树的题目中可以起到意想不到的作用。
声明
对于 pbds 里边的很多神秘东西我总是忘记怎么定义。
这个东西并没有被包含到万能头里边,我们需要再加上万能 Stl 扩展库 #include <bits/extc++.h>
这个东西同样需要 using namespace __gnu_cxx;
这样我们才可以开始用 rope。
这个东西的本质是一个块状链表,大部分操作的复杂度是根号的,而且常数我在使用中觉得虽然大,但是并不是无法让人接受的大,数据范围不太大是可以通过的,所以到时候写不出来平衡树正解不妨使用这个来骗分。
这个东西跟许多 stl 是相近的,都是 bitset<数据类型> 名字(限定长度)
,大部分情况下我们并不需要限定长度,故忽略这个。
一般我们会使用 char 的 rope 和 int 的 rope;
使用
我们先声明了一个 rope 叫做 s
s.push_back(c)
在 s 的末尾处添加字符 c
s.insert(p,x)
在 s 的下标 p 的后边添加 x
s.insert(p,q,n)
将字符串 q 的前 n 位插入 s 的下标 p 处。
注意这里的 q 最好写成 q.c_str()
。
s.erase(p,x)
从 s 的下标 p 开始删除 x 个元素。
s.replace(p,q)
从 s 的下标 p 开始换成 q
s.copy(p,n,q)
从 s 的下标 p 开始的 n 个字符替换成字符串 q
s.substr(p,x)
从 s 的下标 p 开始截取 x 个元素
访问可以直接使用 []
s.append(q,p,n)
q 从下标 p 开始的 n 个字符连接到s的末尾