题解：P13981 数列分块入门 6

· · 题解

这篇题解介绍一个 c++ 自带的数据结构。

做法

在bits/extc++.h这个头文件中有一个命名空间__gnu_cxx。这个命名空间里有一个数据结构叫做rope。这个东西实现的是块状链表，但是他的实现其实是通过可持久化平衡树实现的。在这道题中，我们需要调用 3 个函数。

  1. push_back。这个函数的用法和vector一样。
  2. insert。这个函数的用法是insert(x,k)，表示在 x 这个位置前插入 k。
  3. at。这个函数是用来查询一个位置上的值的。

代码

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define debug(x) cerr<<x<<'\n'
using namespace std;
const int N=2e5+5;
int n;
__gnu_cxx::rope<int>a;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    rep(i,1,n){
        int x;cin>>x;
        a.push_back(x);
    }
    rep(i,1,n){
        int op;cin>>op;
        if(!op){
            int l,r;cin>>l>>r;
            a.insert(l-1,r);
        }
        else{
            int r;cin>>r;
            cout<<a.at(r-1)<<'\n';
        }
    }
    return 0;
}