[Non] 字符串问题

字符串问题

大意

插入字符，查询字符。
初始串 \(s\), \(|s| \le 10^6\)。

思路

可以用平衡树，但是我选择更为强势的 STL 中的 rope。

头文件：#include<ext/rope>

crope r1;           // 存储 char 的 rope
wrope r2;           // 存储 wchar_t 的 rope
rope<long long> r3; // 也可以存储其他基本类型

rope 的大部分操作复杂度均为 \(O(\log n)\)，底层基于可持久化平衡树实现。

函数名	功能描述	示例用法
push_back(x)	在末尾添加单个字符	r.push_back('a');
append(s)	在末尾追加字符串/rope	r.append("abc");
insert(pos, s)	在 pos 位置插入字符串/rope	r.insert(2, "xyz");
erase(pos, n)	从 pos 开始删除 n 个字符	r.erase(1, 10);
replace(pos, n, s)	将 pos 起 n 个字符替换为 s	r.replace(1, 2, "ok");
substr(pos, n)	提取从 pos 开始的 n 个字符	crope sub = r.substr(2, 3);
at(i) 或 [i]	访问下标为 i 的字符	char c = r[0];
size()	返回当前长度	int len = r.size();

---

rope 最强大的特性在于它支持 \(O(1)\) 的对象拷贝，这使得它能以极低的时间和空间成本维护历史版本。

当你将一个 rope 赋值给另一个时，底层并不拷贝树结构，而是增加引用计数。只有在其中一个对象发生修改时，才会局部复制受影响的节点。

crope r1 = "v1_data"; 
crope r2 = r1;         // O(1) 拷贝，此时 r1 和 r2 共享底层节点
r2.insert(0, "new_");  // 修改 r2，r1 保持不变（自动实现可持久化）

如果题目要求查询“第 k 次操作后的状态”，可以直接开一个 rope 数组记录快照：

crope history[MAX_VERSION];int main() {history[0] = "initial_state"; // 初始状态for(int i = 1;i <= m;++ i){history[i] = history[i - 1]; // O(1) 继承上一个版本// 在当前版本上进行操作int opt, pos; char c;cin >> opt >> pos >> c;if(opt == 1){// 修改当前版本，不会影响 history[i - 1]history[i].insert(pos, c);}}
}

记得加：using namespace __gnu_cxx;

代码

#include<iostream>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;string s;
int m;
crope r;int main(){cin >> s;cin >> m;r.append(s.c_str());while(m --){char op;cin >> op;if(op == 'I'){char c; int p; cin >> c >> p;if(p > r.size()){r.append(c);}else{r.insert(p - 1, crope(1, c));}}else{int x; cin >> x;cout << r[x - 1] << '\n';}}return 0;
}