题解：P13981 数列分块入门 6

dvsfanjo · 2025-09-07 13:14:26 · 题解

题解：P13981 数列分块入门 6

solution

使用 pb_ds 库中的 rope 解决。

介绍一下 rope

rope 是 pb_ds 库中的一个分支，内部是一个块状链表，支持可持久化。

需要 #include <bits/extc++.h> 和 using namespace __gnu_cxx;。

rope 的使用

可以直接使用 rope <int> a 来声明一个叫做 a 的 rope 。

a.append(x) 可以在 rope 后面添加一个元素 x，类似于 vector 。

a[x] 可以询问 rope 中下标为 x 的元素，默认下标从 0 开始。

a.insert(x, y) 可以在下标为 x 的位置前插入元素 y。

code

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
int n, op, l, r, c;
rope <int> a;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    a.append(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c;
        a.append(c);
    }
    for (int i = 1; i <= n; i++) {
        cin >> op;
        if (op) {
            cin >> c;
            cout << a[c] << '\n';
        } else {
            cin >> l >> r;
            a.insert(l, r);
        }
    }
    return 0;
}