bzoj1269 [AHOI2006]文本编辑器editor

bzoj1269 [AHOI2006]文本编辑器editor

​​‎

Description

这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义： 文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。 编写一个程序： 建立一个空的文本编辑器。 从输入文件中读入一些操作指令并执行。 对所有执行过的GET操作，将指定的内容写入输出文件。 Input

输入文件中第一行是指令条数N，以下是需要执行的N个操作。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 Output

依次对应输入文件中每条GET指令的输出，不得有任何多余的字符。 Sample Input 10 Insert 13 Balanced eert Move 2 Delete 5 Next Insert 7 editor Move 0 Get Move 11 Rotate 4 Get Sample Output B t

HINT

对输入数据我们有如下假定： MOVE操作不超过50 000个，INSERT、DELETE和ROTATE操作作的总个数不超过6 000，GET操作不超过20 000个，PREV和NEXT操作的总个数不超过20 000。 所有INSERT插入的字符数之和不超过2M（1M=1 024*1 024）。 DELETE操作、ROTATE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。 输入文件没有错误。 Source

鸣谢seter重新制作数据

基本同bzoj1507 添加了反转操作

​​N 2200000 using namespace std;int id[N],n,size[N],fa[N],c[N][2],rev[N],root,cnt;char op[10],v[N],ch[N];inline void update(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+1;}inline void build(int f,int l,int r){ if (l>r) return; int mid=l+r>>1;int now=id[mid];v[now]=ch[mid]; fa[now]=id[f];c[id[f]][mid>f]=now;v[now]=ch[mid]; if (l==r){size[now]=1;return;} build(mid,l,mid-1);build(mid,mid+1,r);update(id[mid]);}inline void pushdown(int x){ if (!rev[x]) return; int l=c[x][0],r=c[x][1]; rev[l]^=1;rev[r]^=1;rev[x]=0; swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);}inline int find(int x,int sz){ pushdown(x); int l=c[x][0],r=c[x][1];if(size[l]+1==sz) return x; if (sz<=size[l]) return find(l,sz);else return find(r,sz-size[l]-1);}inline void rotate(int x,int &tar){ int y=fa[x],z=fa[y]; if (y==tar) tar=x;else c[z][c[z][1]==y]=x; int l=c[y][1]==x,r=l^1; fa[x]=z;fa[c[x][r]]=y;fa[y]=x; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);}inline void splay(int x,int &tar){ while(x!=tar){ int y=fa[x],z=fa[y]; if (y!=tar) { if(c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar); }rotate(x,tar); }}inline int split(int x,int y){ int xx=find(root,x),yy=find(root,y); splay(yy,root);splay(xx,c[root][0]);return c[xx][1];}inline void print(int x){ if (c[x][0]) print(c[x][0]); printf("%c",v[x],size[x]); if(c[x][1]) print(c[x][1]);}int main(){ freopen("bzoj1269.in","r",stdin); scanf("%d",&n);id[1]=1;id[2]=2;cnt=2; build(0,1,2);int pos=1,x=0;root=id[1]; for (int i=1;i<=n;++i){ scanf("%s",op); if (op[0]=='I'){ scanf("%d%*c",&x);int st=0; while(1){ ch[st+1]=getchar(); if (ch[st+1]!='\n'&&ch[st+1]!='\r') {++st;if (st==x) break;} }for (int i=1;i<=x;++i) id[i]=++cnt;build(0,1,x); int xx=find(root,pos),yy=find(root,pos+1);splay(yy,root);splay(xx,c[root][0]); int now=id[1+x>>1];fa[now]=xx;c[xx][1]=now;update(xx);splay(now,root);//printf("%d\n",root); } if (op[0]=='M') {scanf("%d",&x);pos=x+1;}//if (i==8) printf("%d\n",pos); if (op[0]=='P') --pos;if (op[0]=='N') ++pos; if (op[0]=='D'){ scanf("%d",&x); int tmp=split(pos,pos+x+1);c[fa[tmp]][1]=0;update(fa[tmp]);splay(fa[tmp],root); } if (op[0]=='G'){printf("%c",v[find(root,pos+1)]);puts("");} if (op[0]=='R'){scanf("%d",&x);int tmp=split(pos,pos+x+1); rev[tmp]^=1;swap(c[tmp][0],c[tmp][1]);} // print(root);puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。