Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3678 Solved: 1380
Description
这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义： ![Bzoj1269 [AHOI2006]文本编辑器editor](https://image.shishitao.com:8440/aHR0cDovL3d3dy5seWRzeS5jb20vSnVkZ2VPbmxpbmUvaW1hZ2VzLzEyNjdfMS5qcGc%3D.jpg?w=700 "Bzoj1269 [AHOI2006]文本编辑器editor")
![Bzoj1269 [AHOI2006]文本编辑器editor](https://image.shishitao.com:8440/aHR0cDovL3d3dy5seWRzeS5jb20vSnVkZ2VPbmxpbmUvaW1hZ2VzLzEyNjdfMi5qcGc%3D.jpg?w=700 "Bzoj1269 [AHOI2006]文本编辑器editor")
文本：由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
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get
Sample Output
B
t
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
Splay树
肝过维修数列之后，这文本编辑器还是比较好写的。
总之就是各种模拟操作。
第一遍数组开小了T了，开大数组之后WAWAWA
左看右看找不出错，就试着改读入格式。
调了半个多小时无果，觉得有哪里不对。
好像每输出一个字符是要换行的……说好的“对应输入文件中每条GET指令的输出，不得有任何多余的字符”呢？
加个换行就过了，理论上是2A（强行）
不过改了读入之后，时间从2000ms降到了1700+ms （虽然还是好大）
原代码：
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct node{
int ch[];
bool rev;
int w,fa,size;
}t[mxn];
int a[mxn];
int root,cnt=;
int cpos=;//模拟光标
void pushdown(int x){
if(t[x].rev){
swap(t[x].ch[],t[x].ch[]);
t[t[x].ch[]].rev^=; t[t[x].ch[]].rev^=;
t[x].rev=;
}
return;
}
void pushup(int x){
t[x].size=t[t[x].ch[]].size+t[t[x].ch[]].size+;return;
}
void rotate(int x,int &k){
// printf("rotate:%d %d\n",x,k);
int y=t[x].fa,z=t[y].fa,lc,rc;
if(t[y].ch[]==x)lc=;else lc=; rc=lc^;
if(y==k)k=x;
else t[z].ch[t[z].ch[]==y]=x;
t[x].fa=z;t[y].fa=x;t[t[x].ch[rc]].fa=y;
t[y].ch[lc]=t[x].ch[rc];t[x].ch[rc]=y;
pushup(y);
// pushup(x);
return;
}
void Splay(int x,int &k){
pushdown(x);
while(x!=k){
int y=t[x].fa;int z=t[y].fa;
if(y!=k)
if((t[z].ch[]==y)^(t[y].ch[]==x))rotate(x,k);
else rotate(y,k);
rotate(x,k);
}
pushup(x);
return;
}
int st[mxn],top=; int newnode(int x){
int tmp;
if(top)tmp=st[top--];
else tmp=++cnt;
t[tmp].ch[]=t[tmp].ch[]=;
t[tmp].size=;t[tmp].w=x;
t[tmp].rev=;
return tmp;
}
int Build(int l,int r,int fa){
if(l>r)return ;
int mid=(l+r)>>;
int rt=newnode(a[mid]);
t[rt].ch[]=Build(l,mid-,rt);
t[rt].ch[]=Build(mid+,r,rt);
t[rt].fa=fa;
pushup(rt);
return rt;
}
void split(int x,int y){
Splay(x,root);
Splay(y,t[x].ch[]);
return;
}
int find(int x,int w){
if(t[x].rev)pushdown(x);
// printf("rt:%d lc:%d rc:%d sz:%d %d\n",x,t[x].ch[0],t[x].ch[1],t[x].size,w);
if(w<=t[t[x].ch[]].size)return find(t[x].ch[],w);
if(w==t[t[x].ch[]].size+)return x;
return find(t[x].ch[],w-t[t[x].ch[]].size-);
}
void insert(int pos){
int n=read();
for(int i=;i<=n;i++)
a[i]=getchar();
int tmp=Build(,n,);
int x=find(root,pos),y=find(root,pos+);
split(x,y);
t[y].ch[]=tmp;
t[tmp].fa=y;
pushup(y);pushup(x);
// printf("finished\n");
// for(int i=1;i<=n;i++)printf("%c",a[i]);
// printf("\n");
return;
}
void del(int &x){
if(!x)return;
// printf("del:%d\n",x);
t[t[x].fa].size-=t[x].size;
t[x].fa=;
st[++top]=x;
del(t[x].ch[]);del(t[x].ch[]);
x=;
return;
}
void Dele(int pos,int len){
int x=find(root,pos),y=find(root,pos+len+);
// printf("%d %d\n",x,y);
split(x,y);
del(t[y].ch[]);
return;
}
void reverse(int pos,int len){
int x=find(root,pos),y=find(root,pos+len+);
split(x,y);
t[t[y].ch[]].rev^=;
pushdown(t[y].ch[]);
return;
}
void Debug(int x){
if(t[x].ch[])Debug(t[x].ch[]);
if(t[x].w)printf("%c",t[x].w);
if(t[x].ch[])Debug(t[x].ch[]);
return;
}
void Get(){
// for(int i=0;i<=cnt;i++){
// printf("rt:%d lc:%d rc:%d\n",i,t[i].ch[0],t[i].ch[1]);
// printf("fa:%d sz:%d w:%d\n",t[i].fa,t[i].size,t[i].w);
// printf("\n");
// } int x=find(root,cpos+);
if(t[x].w)printf("%c\n",t[x].w);
else puts(" ");
return;
}
int n;
int main(){
int i,j,x;
int st=,ed=;
n=read();
char op[];
cpos=;
root=Build(,,);
// printf("fin\n");
st=find(root,);
ed=find(root,);
while(n--){
scanf("%s",op);
switch(op[]){
case 'M':{
x=read();
cpos=x+;
break;
}
case 'I':{
insert(cpos);
break;
}
case 'D':{
x=read();
Dele(cpos,x);
break;
}
case 'R':{
x=read();
reverse(cpos,x);
break;
}
case 'G':{Get();break;}
case 'P':{cpos--;break;}
case 'N':{cpos++;break;}
// case 'K':{printf("root:%d\n",root);Debug(root);break;}
}
}
return ;
}
从阿当学长那学到的读入方式：
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
struct node{
int ch[];
bool rev;
int w,fa,size;
}t[mxn];
char a[];
int root,cnt=;
int cpos=;//模拟光标
void pushdown(int x){
if(t[x].rev){
swap(t[x].ch[],t[x].ch[]);
t[t[x].ch[]].rev^=; t[t[x].ch[]].rev^=;
t[x].rev=;
}
return;
}
void pushup(int x){
t[x].size=t[t[x].ch[]].size+t[t[x].ch[]].size+;return;
}
void rotate(int x,int &k){
int y=t[x].fa,z=t[y].fa,lc,rc;
if(t[y].ch[]==x)lc=;else lc=; rc=lc^;
if(y==k)k=x;
else t[z].ch[t[z].ch[]==y]=x;
t[x].fa=z;t[y].fa=x;t[t[x].ch[rc]].fa=y;
t[y].ch[lc]=t[x].ch[rc];t[x].ch[rc]=y;
pushup(y);
return;
}
void Splay(int x,int &k){
pushdown(x);
while(x!=k){
int y=t[x].fa;int z=t[y].fa;
if(y!=k)
if((t[z].ch[]==y)^(t[y].ch[]==x))rotate(x,k);
else rotate(y,k);
rotate(x,k);
}
pushup(x);
return;
}
int st[mxn],top=; int newnode(int x){
int tmp;
if(top)tmp=st[top--];
else tmp=++cnt;
t[tmp].ch[]=t[tmp].ch[]=;
t[tmp].size=;t[tmp].w=x;
t[tmp].rev=;
return tmp;
}
int Build(int l,int r,int fa){
if(l>r)return ;
int mid=(l+r)>>;
int rt=newnode(a[mid]);
t[rt].ch[]=Build(l,mid-,rt);
t[rt].ch[]=Build(mid+,r,rt);
t[rt].fa=fa;
pushup(rt);
return rt;
}
void split(int x,int y){
Splay(x,root);
Splay(y,t[x].ch[]);
return;
}
int find(int x,int w){
if(t[x].rev)pushdown(x);
if(w<=t[t[x].ch[]].size)return find(t[x].ch[],w);
if(w==t[t[x].ch[]].size+)return x;
return find(t[x].ch[],w-t[t[x].ch[]].size-);
}
void Debug(int x){
if(t[x].ch[])Debug(t[x].ch[]);
if(t[x].w)printf("%c",t[x].w);
if(t[x].ch[])Debug(t[x].ch[]);
return;
}
void insert(int pos){
int n;scanf("%d%*c",&n);
gets(a+);
int tmp=Build(,n,);
int x=find(root,pos),y=find(root,pos+);
split(x,y);
t[y].ch[]=tmp;
t[tmp].fa=y;
pushup(y);pushup(x);
return;
}
void del(int &x){
if(!x)return;
t[t[x].fa].size-=t[x].size;
t[x].fa=;
st[++top]=x;
del(t[x].ch[]);del(t[x].ch[]);
x=;
return;
}
void Dele(int pos,int len){
int x=find(root,pos),y=find(root,pos+len+);
split(x,y);
del(t[y].ch[]);
return;
}
void reverse(int pos,int len){
int x=find(root,pos),y=find(root,pos+len+);
split(x,y);
t[t[y].ch[]].rev^=;
pushdown(t[y].ch[]);
return;
} void Get(){
int x=find(root,cpos+);
if(t[x].w)printf("%c\n",t[x].w);
else puts(" ");
return;
}
int n;
int main(){
int i,j,x;int st=,ed=;
scanf("%d%*c",&n);
char op[];
cpos=;
a[]=a[]=;
root=Build(,,);
st=find(root,);ed=find(root,);
while(n--){
scanf("%s%*c",op);
switch(op[]){
case 'M':{scanf("%d%*c",&x);cpos=x+;break;}
case 'I':{insert(cpos);break;}
case 'D':{scanf("%d%*c",&x);Dele(cpos,x);break;}
case 'R':{scanf("%d%*c",&x);reverse(cpos,x);break;}
case 'G':{Get();break;}
case 'P':{cpos--;break;}
case 'N':{cpos++;break;}
}
}
return ;
}