0%

STL rope

发表于 更新于 分类于 ，

主要内容参考自:Mrsrz的博客

2018 nowcoder多校 第三场 C题

题意为有1—N张卡片按照顺序由top至bottom,现给出M次操作:对给出的 ，视为将现在序列的i-th号卡片开始的j张卡片放到顶端,要求给出最终顺序

不少人使用了rope,研究后觉得非常好,做了一些了解与学习。

rope意思为重绳与string对应,但也可以保存其他类型,用可持久化平衡树实现

不是标准STL里的东西，属于STL扩展

定义:

1
2
3
#include 

using namespace __gnu_cxx;

rope的基本操作:基本都是O(logn)的

1
2
3
4
5
6
7
8
9
10
11
rope<int>x;
x.length()              //返回x的大小
x.size()                //返回x的大小
x.push_back(s)          //在末尾添加s
x.insert(pos,s)         //在pos位置插入s
x.erase(pos,x)          //从pos位置开始删除x个
x.replace(pos,s)        //将位置为pos的元素换成s
x.substr(pos,x)         //从pos位置开始提取x个元素
x.copy(pos,x,s)         //将从pos位置开始x个元素提取到s中
x.at(x)                 //访问第x个元素
x.at[x]                 //访问第x个元素

可持久化的方法:

1
2
rope<int> *f[10000];
f[i]=new rope<int>(*f[i-1]);

关于翻转平衡树,都说是维护一正一反两个rope，翻转就把两个rope交换一下
之后尝试一下。

过题代码,不过比手写的Splay要慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include 
#include 
using namespace __gnu_cxx;
using namespace std;
const int maxn = 1e5 + 10;
rope<int> T;
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        T.push_back(i + 1);
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        T = T.substr(a - 1, b) + T.substr(0, a - 1) + T.substr(a - 1 + b, n - b - a + 1);
    }
    printf("%d", T[0]);
    for (int i = 1; i < n; ++i) {
        printf(" %d", T[i]);
    }
    return 0;
}