Shuffle Cards (牛客多校) (rope 块状链表 用作可持续优化平衡树, 用于区间的整体移动操作(可以类比于字符串))

发布时间 2023-06-28 12:32:24作者: VxiaohuanV

rope:

#include<ext/rope>

using namespace __gnu_cxx; 

定义方法:rope<变量类型>变量名称;

人话解释:超级string

算法解释:块状链表(即讲链表与数组的优势结合,形成分块思想)

用途解释:这本来是一个用于快速操作string的工具,却一般被定义成int,然后用作可持久化线段树!

insert(int pos, string &s, int n) 将字符串s的前n位插入rope的下标pos处,如没有参数n则将字符串s的所有位都插入rope的下标pos处 (补充地址知识:如果你不想从字符串下标为0(即第一个字符)的地址开始取n位,就将你想开始取的地址代入。如s+1表示从字符串下标为1(即第二个字符)的地址开始取n位。int、char等变量类型的数组都适用这种方法来更改数组操作的起始位置。)

substr(int pos, int len) 提取rope的从下标pos开始的len个字符

at(int x) 访问rope的下标为x的元素

erase(int pos, int num) 从rope的下标pos开始删除num个字符

copy(int pos, int len, string &s) 从rope的下标pos开始的len个字符用字符串s代替,如果pos后的位数不够就补足

replace(int pos, string &x);//从rope的下标pos开始替换成字符串x,x的长度为从pos开始替换的位数,如果pos后的位数不够就补足

 

一般用 substr 即可 

 

题目大意:

  • 给一个牌堆,  然后m次操作,
  • 每次操作可以选择 l-r的牌 放到牌堆顶部
  • 问最后的牌堆样子

 思路;

  • 利用 C++ 自带的 rope