UVA12538 题解

ikunTLE · 2024-11-28 22:37:11 · 题解

题目传送门

思路

本题可以使用 rope 解决。

发现本题需要维护一个插入、删除、查找历史版本的数据结构，可以使用可持久化平衡树实现。但是，以上功能其实在 pd_ds 库中已经实现了。那么这道题就成为 rope 的模板题了。

下面介绍一下 rope 的基本语法。

rope 的头文件在 ext/rope 中，但由于它不是一个标准 STL 库，还需要引用命名空间 __gnu_cxx。

rope 定义声明方式：crope rp;，在本题中会用到一下的操作：

• rp.insert(p,s)：在下标 p 后插入字符串 s。
• rp.erase(p,n)：从下标 p 开始删除 n 个字符。
• rp.substr(p,n)：从下标 p 开始截取 n 个字符。
• rp.count(rp.begin(),rp.end(),ch) 在 rp 中统计字符 ch 的个数。

AC CODE

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e4+10;
crope x,s[N];
char rd[N];
int main(){
    int n=read(),cnt=0,sum=0;
    while(n--){
        int op=read();
        if(op==1){
            int p=read()-sum;
            scanf("%s",rd);
            x.insert(p,rd);
            s[++cnt]=x;
        }
        else if(op==2){
            int p=read()-sum,c=read()-sum;
            x.erase(p-1,c);
            s[++cnt]=x;
        }
        else{
            int v=read()-sum,p=read()-sum,c=read()-sum;
            crope temp=s[v].substr(p-1,c);
            sum+=count(temp.begin(),temp.end(),'c');
            for(char ch:temp)
                putchar(ch);
            putchar('\n');
        }
    }
    return 0;
}