题解 P3850 【[TJOI2007]书架】

critnos · 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;
    }   
}