SP29455 题解

· · 题解

哇塞，各位神犇都用 FHQ Treap 和 Splay 啊，我都不会 qwq 。

但是，知识不够，魔法来凑，在我们万千 OIer 们所追捧的 STL ……的兄弟 pd_ds 库中，有这样一个冷门但是好用的容器—— rope ！

关于 rope 的实现，说是可持久化平衡树 + 块状链表，咱都不知道。而且空间复杂度十分玄学。但毕竟前人已经帮我们封装好了，咱也就先用着吧，就是常数会比较大。

我们要用到的 rope 类的成员函数和成员运算符只有重载 + 、重载 [] 、和 substr() 、 size() ，具体对更多常用操作的介绍放在代码后面附的注释里面啦。

rope 时间复杂度：O(n\sqrt{n})

rope 空间复杂度：O(?) 也别喷，我也不清楚，反正消耗的空间很小，去掉常数大概是 O(\sqrt{n}) ，但是链表的大小十分玄学，还有其它的常数消耗。

//注：我们尚且不知道 rope 在 NOI 系列竞赛能否使用，请谨慎为好！
#include<bits/stdc++.h>
#include<ext/rope>//头文件 <bits/extc++.h> 也可以
using namespace std;
using namespace __gnu_cxx;//rope 不是 std 命名空间的内容

rope<char>r;//基本等于 crope r
int n,t,x,y,cnt;
char str[100010];//注意只能 char 数组不能 string （记得开大一点 QAQ ）

int main(){
    scanf("%s%d",str,&n);
    r.insert(0,str);
    while(n--){
        scanf("%d%d",&t,&x);
        switch(t){
            case 1:
                scanf("%d",&y);
                r=r.substr(x,y-x+1)+r.substr(0,x)+r.substr(y+1,r.size()-y-1);
            break;
            case 2:
                scanf("%d",&y);
                r=r.substr(0,x)+r.substr(y+1,r.size()-y-1)+r.substr(x,y-x+1);
            break;
            case 3:
                printf("%c\n",r[x]);
            break;
        }
    }
}
/*附：常用 rope 操作（假设叫 x ）
    x.length()/x.size() ：返回 x 元素个数；
    x.push_back(y)/x.append(y) ：在末尾添加 y ；
    x.insert(pos,y) ：在 pos 插入 y；
    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 个元素。

    哦对了， rope 之间的赋值是 O(1) 的，可以很方便的实现可持久化数据结构。（水题咕值++ （划掉
*/

UPD on 2022/10/18 17:06 更正 1 处不规范的地方，感谢@qwasd ！