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

sswyhprays · 2025-09-11 18:53:02 · 题解

rope 学习笔记 & Version Controlled IDE 题解

神级 STL 之 rope

内部构造是块状链表，可平替各种可持久化数据结构。

rope 包括在 ext/rope 库，命名空间 __gnu_cxx 中。

crope 可以定义一个字符串 rope，等效于 rope<char>。crope 的常用操作如下：

• a[x]：访问 a 中下标为 x 的元素；
• a.push_back(x)：在 a 的末尾添加字符 c；
• a.insert(p,x)：在 a 的下标 p 后面添加 x；
• a.erase(p,x)：从 a 的下标 p 开始删除 x 个元素；
• a.replace(p,s)：从 a 的下标 p 开始换成字符串 s；
• a.substr(p,x)：从 a 的下标 p 开始截取 x 个元素；
• a.append(s)：把字符串 s 连接到 a 的结尾。

Version Controlled IDE 题解

一般定义一个 crope 数组来记录历史版本。

都用 crope 了那还说啥了，就本题而言紫 -> 橙，STL 大法好。

注意，insert 的第二个参数类型不能是 string，应用 char 数组。

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

const int MAXN = 5e5 + 5;

int n;
int op, p, c, v;
int cnt, subt = 0;
char ss[MAXN];
crope cur;
crope vers[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    while (n--)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> p;
            cin >> ss;
            p -= subt;
            cur.insert(p, ss);
            vers[++cnt] = cur;
        }
        else if (op == 2)
        {
            cin >> p >> c;
            p -= subt, c -= subt;
            cur.erase(p - 1, c);
            vers[++cnt] = cur;
        }
        else
        {
            crope t;
            cin >> v >> p >> c;
            p -= 1;
            v -= subt, p -= subt, c -= subt;
            t = vers[v].substr(p, c);
            for (int i = 0; i < t.size(); i++)
            {
                if (t[i] == 'c')
                {
                    subt++;
                }
            }
            cout << t << '\n';
        }
    }

    return 0;
}