//rope不会超时
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;cin>>n;
	rope<int> a;
	for(int i=1,x;i<=n;i++) cin>>x,a.push_back(x);
	for(int i=1,op,l,r,c;i<=n;i++)
	{
		cin>>op>>l>>r>>c;
		if(op==0) a.insert(l-1,r);
		else cout<<a[r-1]<<'\n';
	}
	return 0;
}
/*

//vector会超时
#include<bits/stdc++.h>
using namespace std;
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;cin>>n;
	vector<int> a;
	for(int i=1,x;i<=n;i++) cin>>x,a.push_back(x);
	for(int i=1,op,l,r,c;i<=n;i++)
	{
		cin>>op>>l>>r>>c;
		if(op==0) a.insert(a.begin()+l-1, r);
		else cout<<a[r-1]<<'\n';
	}
	return 0;
}

*/

在 C++ 中，rope 是 GCC 标准库扩展（SGI STL）提供的一种底层基于平衡树（通常是红黑树或树状数组变体）的高效字符串/序列数据结构。

在算法竞赛中，rope 常被称为“可持久化字符串”或“可持久化数组”的神器，因为它支持 $O(\log N)$ 的区间插入、删除、拼接，并且支持 $O(1)$ 的拷贝（实现可持久化/版本控制）。

以下是 rope 的具体使用方法和竞赛避坑指南。

1. 头文件与命名空间

rope 不是 C++ 标准库的一部分，仅在 GCC (libstdc++) 中可用。

#include <ext/rope>
using namespace __gnu_cxx;

通常我们使用 rope<char>，它有一个内置的别名 crope。

2. 核心操作与复杂度

假设 r 是一个 crope，长度为 $N$。

3. 核心特性：$O(1)$ 可持久化（版本控制）

因为 rope 底层是树结构，当你执行 crope r2 = r1; 时，它只是复制了根节点指针，并不会复制整棵树。 当你修改 r2 时，rope 会自动使用路径复制（Copy-On-Write），只创建被修改路径上的新节点，而 r1 依然指向原来的旧节点。这就天然实现了可持久化数组/字符串。

4. 完整示例代码（符合你的代码风格）

下面是一个演示 rope 基本操作和可持久化特性的模板：

#include <bits/stdc++.h>
#include <ext/rope>
#define int long long
using namespace std;
using namespace __gnu_cxx; // 必须引入此命名空间

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    // 1. 定义与初始化
    crope r; 
    r += "hello";
    r.push_back(' ');
    r += "world";
    cout << r << '\n'; // 输出: hello world

    // 2. 插入与删除
    r.insert(5, " beautiful"); // 在索引5处插入
    cout << r << '\n'; // 输出: hello beautiful world
    r.erase(5, 10); // 删除索引5开始的10个字符
    cout << r << '\n'; // 输出: hello world

    // 3. 截取子串与拼接
    crope sub = r.substr(0, 5); // 截取 "hello"
    crope r2 = sub + " C++";
    cout << r2 << '\n'; // 输出: hello C++

    // 4. 随机访问 (只能读，不能写)
    cout << r[0] << '\n'; // 输出: h
    // r[0] = 'H'; // 编译错误！rope的[]返回的是值，不是引用
    
    // 若要修改单个字符，使用 replace
    r.replace(0, 1, "H"); 
    cout << r << '\n'; // 输出: Hello world

    // 5. 可持久化 (版本控制)
    vector<crope> history;
    history.push_back(r); // 保存版本0
    
    r.erase(0, 6); // 修改当前版本，变成 "world"
    history.push_back(r); // 保存版本1
    
    // 历史版本不会被破坏
    cout << history[0] << '\n'; // 输出: Hello world
    cout << history[1] << '\n'; // 输出: world

    return 0;
}

5. 竞赛避坑指南（非常重要！）

1. operator[] 是只读的： r[i] 返回的是 char 的值，而不是引用。所以 r[i] = 'a' 会编译报错。如果需要单点修改，必须用 r.replace(i, 1, "a")。

2. 空间爆炸问题（MLE）： 虽然拷贝是 $O(1)$ 的，但每次修改（insert/erase/replace）都会产生新的树节点。如果你在循环中进行 $10^5$ 次单点修改，底层会产生大量节点，极易导致 MLE。

   • 优化方案：尽量把单点操作合并成区间操作，或者在必须频繁单点修改时，老老实实写可持久化线段树或分块。

3. 不支持 rope<int>： 在大多数 GCC 版本中，rope 主要是为字符类型设计的。rope<int> 可能会编译报错或行为诡异。

   • 替代方案：如果题目要求维护 int 数组（如可持久化数组），且值域在 char 范围内，可以强行转成 char 存；否则请使用可持久化线段树（主席树）或可持久化 Treap。

4. 迭代器极慢： 尽量不要用 for(auto it = r.begin(); it != r.end(); ++it) 去遍历 rope，它的迭代器移动复杂度是 $O(\log N)$，遍历一次总复杂度是 $O(N \log N)$，会 TLE。

   • 正确做法：直接用 for(int i = 0; i < r.size(); i++) r[i]，或者直接用 cout << r 整体输出（底层有优化）。

5. c_str() 的代价： 调用 r.c_str() 会强制将整棵树展平成一个连续的字符数组，复杂度是 $O(N)$。除非最后输出答案，否则不要在循环中调用。

适用题目场景

• 文本编辑器类问题：如洛谷 P3987（永远等待加野井）、Luogu P2073 等，涉及大量光标移动、区间插入、删除。
• 可持久化字符串：需要保留历史版本并进行区间拼接的题目。
• 代替 std::string：当 std::string 的 insert / erase 导致 $O(N^2)$ 超时，且不需要修改单个字符时，直接换成 crope 即可卡常过题。