自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 21:53:23，当前版本为作者最后更新于2020-05-12 15:36:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题感觉用啥方法都能水过去。

比如 vector，块链。

介绍一种神仙级别的 STL 数据结构：rope。

（表面上大概可以理解为进阶版的 vector）

这个丧心病狂的东西支持 $\log n$ 级别的大部分 vector 操作。

然后就很简单了，，，

您以为这是基于平衡树的？

no，是基于可持久化平衡树的，底层是红黑树。

所以支持 $O(1)$ 的 copy，，，

可以水大部分的可持久化题目。

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
rope<int> a; 
string t[200005];
int main()
{
	int n,x;
	string p;
	scanf("%d",&n);
	while(n--)
	{
		cin>>t[a.size()];
		a.push_back(a.size());
	}	
	scanf("%d",&n);
	while(n--)
	{
		cin>>t[a.size()];
		scanf("%d",&x);
		a.insert(x,a.size());
	}
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&x);
		cout<<t[a[x]]<<endl;
	}	
}