【题目描述】
维护一种可持久化的文本编辑器,支持下列操作:
1 p str 在当前版本的第p个字符后插入字符串str,并作为下一版本(数据保证0<=p<=当前字符串的长度,且插入的字符串中只有小写字母)
2 p c 在当前版本中删除从第p个字符开始的后c个字符,并作为下一版本(包含第p个字符,数据保证1<=p<=当前字符串的长度,且p+c-1<=当前字符串的长度)
3 x p c 输出第x个版本从第p个字符开始的后c个字符(包含第p个字符,数据保证1<=p<=第x个版本的字符串的长度,且p+c-1<=第x个版本的字符串的长度)
为了体现在线,你需要维护一个变量d,在3操作之后,d加上你输出字符串中字符'c'的数量,并且在数据中给出的操作1中的p,操作2中的p和c,操作3中的x,p,c均为加上变量d的结果,你需要把它们减去d之后运算
开始时为空串,d=0,且为版本0,每进行操作1,2就会以上一版本的基础上修改形成下一版本
【输入格式】
第一行一个数n,表示有n个操作
下面n行,第一个数字为op,表示操作类型
op=1时表示第一种操作,后面有一个数p和一个字符串str,意义同上面的描述,在操作之前,你需要将p减去d,才能得到正确的p,d的意义同上面的描述,表示你之前第三种操作输出的所有字符串中字符'c'的数量
op=2时表示第二种操作,后面有两个数p,c,意义同上面的描述,在操作之前,你需要将p和c减去d,才能得到正确的p和c,d的意义同上面的描述,表示你之前第三种操作输出的所有字符串中字符'c'的数量
op=3时表示第三种操作,后面有三个数x,p,c,意义同上面的描述,在操作之前,你需要将x,p和c减去d,才能得到正确的x,p和c,d的意义同上面的描述,表示你之前第三种操作输出的所有字符串中字符'c'的数量
【输出格式】
对于每个第三种操作输出一行表示结果
【样例输入】
61 0 abcdefgh2 4 33 1 2 53 3 3 41 4 xy3 5 4 6
【样例输出】
bcdefbcgbxyc
【提示】
对于样例解密的结果为
61 0 abcdefgh2 4 33 1 2 53 2 2 31 2 xy3 3 2 4
本题共20组测试数据,一个点5分,给出数据特征如下
测试点编号 操作数量的规模 插入字符串的特点 插入字符串的最大长度
1 n =500 N/A 10 2 n =1000 N/A 10 3 n =10000 字符只有'a','b' 200 4 n =20000 字符只有'a','b' 200 5 n =30000 字符只有'a','b' 200 6 n =40000 字符只有'a','b' 200 7 n =50000 字符只有'a','b' 200 8 n =100000 字符只有'a','b' 200 9 n =100000 字符只有'a' 200 10 n =100000 字符只有'c' 200 11 n =10000 N/A 200 12 n =20000 N/A 200 13 n =30000 N/A 200 14 n =40000 N/A 200 15 n =50000 N/A 200 16 n =60000 N/A 200 17 n =70000 N/A 200 18 n =80000 N/A 200 19 n =90000 N/A 200 20 n =100000 N/A 200
题解
可持久化Treap模板题。
#include#define MAXN 100010#define lc(x) t[x].l#define rc(x) t[x].rusing namespace std;struct Treap{int l,r,w,s;char v;}t[MAXN*50];int N,tot,root[MAXN],cur,D;char s[MAXN];inline int Copy(int x){t[++tot]=t[x];return tot;}inline int New(char x){t[++tot].v=x;t[tot].w=rand();t[tot].s=1;return tot;}inline void Up(int p){t[p].s=t[lc(p)].s+t[rc(p)].s+1;}void Split(int rt,int k,int &a,int &b){ if(!rt){a=b=0;return;} if(t[lc(rt)].s>=k)b=Copy(rt),Split(lc(b),k,a,lc(b)),Up(b); else a=Copy(rt),Split(rc(a),k-t[lc(rt)].s-1,rc(a),b),Up(a);}int Merge(int x,int y){ if(!x||!y)return x^y; int p; if(t[x].w>t[y].w)p=Copy(x),rc(p)=Merge(rc(p),y); else p=Copy(y),lc(p)=Merge(x,lc(p)); Up(p);return p;}void Build(int &rt,int l,int r){ if(l>r)return; int mid=(l+r)>>1; rt=New(s[mid]); Build(lc(rt),l,mid-1); Build(rc(rt),mid+1,r); Up(rt);}inline void Insert(int &rt,int p){ int x,y,z; Split(rt,p,x,y); Build(z,1,strlen(s+1)); rt=Merge(Merge(x,z),y);}inline void Del(int &rt,int p,int k){ int x,y,z,d; Split(rt,p-1,x,y); Split(y,k,d,z); rt=Merge(x,z);}void Print(int rt){ if(!rt)return; Print(lc(rt)); putchar(t[rt].v); if(t[rt].v=='c')D++; Print(rc(rt));}inline void Query(int rt,int p,int k){ int x,y,z,d; Split(rt,p-1,x,y); Split(y,k,d,z); Print(d); y=Merge(d,z);rt=Merge(x,y); puts("");}int op,x,y,z;int main(){ freopen("persistable_editor.in","r",stdin); freopen("persistable_editor.out","w",stdout); scanf("%d",&N); for(int i=1;i<=N;i++){ scanf("%d%d",&op,&x);x-=D; if(op==1){ cur++;root[cur]=root[cur-1]; scanf("%s",s+1);Insert(root[cur],x); } else if(op==2){ cur++;root[cur]=root[cur-1]; scanf("%d",&y);y-=D;Del(root[cur],x,y); } else{ scanf("%d%d",&y,&z);y-=D;z-=D; Query(root[x],y,z); } } return 0;}