首页 > 代码库 > 洛谷 P1383 codevs 3333 高级打字机
洛谷 P1383 codevs 3333 高级打字机
题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下3种操作：
1.T x：在文章末尾打下一个小写字母x。(type操作)
2.U x：撤销最后的x次修改操作。（Undo操作）
（注意Query操作并不算修改操作）
3.Q x：询问当前文章中第x个字母并输出。（Query操作）
文章一开始可以视为空串。
输入输出格式
输入格式：
第1行：一个整数n，表示操作数量。
以下n行，每行一个命令。保证输入的命令合法。
输出格式：
每行输出一个字母，表示Query操作的答案。
输入输出样例
输入样例#1：
7T aT bT cQ 2U 2T cQ 2
输出样例#1：
bc
说明
【数据范围】
对于40%的数据 n<=200;
对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。
<高级挑战>
对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。
<IOI挑战>
必须使用在线算法完成该题。
源代码
#include<stdio.h>int n;struct tree{ int l,r;//左右儿子指针 char cc;}t[4000010];int root[100010]={0},cnt=1;int len[100010]={0};void updata(int & now,int last,int l,int r,int pos,char c){ now=cnt++; t[now].l=t[last].l; t[now].r=t[last].r; if(l==r) { t[now].cc=c; return; } int mid=l+r>>1; if(pos>mid) { updata(t[now].r,t[last].r,mid+1,r,pos,c); } else { updata(t[now].l,t[last].l,l,mid,pos,c); }}void query(int now,int l,int r,int pos){ if(l==r) { printf("%c\n",t[now].cc); return; } int mid=l+r>>1; if(pos>mid) query(t[now].r,mid+1,r,pos); else query(t[now].l,l,mid,pos);}int main(){ scanf("%d",&n); int t=0; for(int kkk=1;kkk<=n;kkk++) { char mode[3]; scanf("%s",mode); if(mode[0]==‘T‘) { scanf("%s",mode); t++; len[t]=len[t-1]+1; updata(root[t],root[t-1],1,n,len[t],mode[0]); } else if(mode[0]==‘U‘) { int x; scanf("%d",&x); root[t+1]=root[t-x]; len[t+1]=len[t-x]; t++; } else { int pos; scanf("%d",&pos); query(root[t],1,n,pos); } } return 0;}
洛谷 P1383 codevs 3333 高级打字机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。