http://www.elijahqi.win/2018/01/23/bzoj1269/
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 添加了反转操作
http://www.elijahqi.win/2018/01/23/bzoj1507-noi2003editor/
#include<cstdio>#include<cstring>
#include<algorithm>
#define 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;
}