Rope 真的是一個(gè)非常好用的東西，在非常多的平衡樹的題目中可以起到意想不到的作用。

聲明

對(duì)于 pbds 里邊的很多神秘東西我總是忘記怎么定義。

這個(gè)東西并沒有被包含到萬(wàn)能頭里邊，我們需要再加上萬(wàn)能 Stl 擴(kuò)展庫(kù) #include <bits/extc++.h>

這個(gè)東西同樣需要 using namespace __gnu_cxx;

這樣我們才可以開始用 rope。

這個(gè)東西的本質(zhì)是一個(gè)塊狀鏈表，大部分操作的復(fù)雜度是根號(hào)的，而且常數(shù)我在使用中覺得雖然大，但是并不是無(wú)法讓人接受的大，數(shù)據(jù)范圍不太大是可以通過的，所以到時(shí)候?qū)懖怀鰜砥胶鈽湔獠环潦褂眠@個(gè)來騙分。

這個(gè)東西跟許多 stl 是相近的，都是 bitset<數(shù)據(jù)類型> 名字(限定長(zhǎng)度)，大部分情況下我們并不需要限定長(zhǎng)度，故忽略這個(gè)。

一般我們會(huì)使用 char 的 rope 和 int 的 rope;

使用

我們先聲明了一個(gè) rope 叫做 s

s.push_back(c) 在 s 的末尾處添加字符 c

s.insert(p,x) 在 s 的下標(biāo) p 的后邊添加 x

s.insert(p,q,n) 將字符串 q 的前 n 位插入 s 的下標(biāo) p 處。

注意這里的 q 最好寫成 q.c_str()。

s.erase(p,x) 從 s 的下標(biāo) p 開始刪除 x 個(gè)元素。

s.replace(p,q) 從 s 的下標(biāo) p 開始換成 q

s.copy(p,n,q) 從 s 的下標(biāo) p 開始的 n 個(gè)字符替換成字符串 q

s.substr(p,x) 從 s 的下標(biāo) p 開始截取 x 個(gè)元素

訪問可以直接使用 []

s.append(q,p,n) q 從下標(biāo) p 開始的 n 個(gè)字符連接到s的末尾