UVA12538 自带版本控制功能的IDE Version Controlled IDE

XichenOC · 2025-01-21 21:27:06 · 题解

自带版本控制功能的 IDE Version Controlled IDE

题目翻译：

题目比较简单明了，直接在原题看即可。

又是一道可以用 rope 水掉的紫题

所以什么是 rope？

简介：

他是一个 STL 中自带的一种数据结构，是 pb_ds（Policy-Based Data Structures）库 的一个分支，由于他的底层是可持久化平衡树——红黑树，或块状链表。所以他的操作的复杂度几乎约等于 O(\log n) 或 \sqrt n。它可支持操作较多，完全可以理解成加强版的 vector。

最为抽象的是，它可以几乎以 O(1) 的复杂度复制一份，且空间消耗不算太大，这导致他可以代替实现繁琐的可持久化平衡树、可持久化线段树（主席树）、可持久化并查集等等。

其可以以很小的代码量和调试难度骗得较高得分，且 noip 可以使用。

使用方法：

准备：

对与 rope 的使用必须要要调用其库和名名空间名。（因为它不包含在万能头中，且不是 std 命名）

#include<ext/rope>
using namespace __gnu_cxx;

定义：

其定义方式与其他 STL 的定义方式相同，如 rope<int>a。若要定义一个字符 rope 可以rope<char>c 或 crope c，其类似与一个字符串。

操作：

字符串 rope（crope）

首先，我们定义了一个 crope a;

• a.push_back(x)：在 a 的末尾添加字符 c；
• a.insert(p,x): 在 a 的下标 p 后面添加 x；
• 或 a.insert(p,s,n)：将字符串 s 的前 n 位插入 a 的下标 p 处；
• a.erase(p,x): 从 a 的下标 p 开始删除 x 个元素；
• a.replace(p,s): 从 a 的下标 p 开始换成字符串 s，若 a 的位数不够则补足；
• a.copy(p,n,s)：从 a 的下标 p 开始的 n 个字符换成字符串 s，若位数不够则补足；
• a.substr(p,x)：从 a 的下标 p 开始截取 x 个元素；
• a[x] 或 a.at(x) 访问下标为 x 的元素；
• a.append(s,p,n)：把字符串 s 中从下标 p 开始的 n 个字符连接到 a 的结尾，如没有参数 n 则把字符串 s 中下标 p 后的所有字符连接到 a 的结尾，如参数 p 也没有则把整个字符串 s 连接到 a 的结尾；

以上，s 均为字符串（string 或 char[]）类型，c 为字符（char）类型，n，p，x 均为整型。

数组 rope（rope<int>）

和字符串 rope 的操作差不多，只是把上文中的字符串参数换成了数组。

数组 rope 可以用 a.append(x) 来在末尾插入一个数 x，当然也可以用类似于上文的方法把一个数组连接到末尾，这里不再赘述。

数组 rope 也支持 substr 操作，用于截取其中的一段数。

其他常用操作：

与其他普通的 STL 一样支持：

• size()：返回大小；
• empty()：返回是否为空；
• begin()：返回首指针；
• end()：返回末尾指针后一位；
• clear()：清空该 rope；

  可持久操作：

  可持久操作主要分为两种，朴素版和指针版，由于复杂度差不多，且指针版可能不太好理解 可能是我菜，这里主要将朴素版。

我们定义两个 rope 一个为 now 和 past 分别表示当前正在维护的，和之前的版本。对于每一次操作结束后都可以将 past[++cnt]=now（没错直接等于就 O(1) 复制了）其中 cnt 为版本数。这样需要调用时就直接找到历史版本查询即可。

本题思路：

用一个 past[cnt] 的 rope 来储存历史版本，没修改一次就储存一次，再用 now 来储存当前版本，其余操作没有什么区别。

完整代码

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N=5e4+10;
char s[N];
int cnt,d;
crope now,past[N];
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int p;
            scanf("%d",&p);
            p-=d;
            scanf("%s",s);
            now.insert(p,s);
            past[++cnt]=now;
        }
        else if(op==2){
            int p,c;
            scanf("%d%d",&p,&c);
            p-=d;
            c-=d;
            now.erase(p-1,c);
            past[++cnt]=now;
        }
        else if(op==3){
            int v,p,c;
            scanf("%d%d%d",&v,&p,&c);
            v-=d;
            p-=d;
            c-=d;
            crope ans=past[v].substr(p-1,c);
            d+=count(ans.begin(),ans.end(),'c');
            cout<<ans<<endl;
        }
    }
}

rope 讲解