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