[文章目录]
Description
这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义： 
两道题差不多，就一起写了。RE了n遍，原因是数组开小了，2M QAQ...
说实话没什么难度，不过自己把zig与zag合并成了一个rotate，然后，旋转的代码就短了辣么多。开心。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int m,n,now;
char st[1000],a[3001000],ch;
struct node
{
node *fa,*c[2];
bool tur;
char val;
int size;
node();
void reverse();
void push_up();
void push_down();
}*null=new node(),*root=new node();
node :: node()
{
fa=c[0]=c[1]=null;
size=null?1:0;
val=1; tur=false;
}
void node :: reverse()
{
swap(c[0],c[1]);
tur^=1;
}
void node :: push_up()
{
size=c[0]->size+c[1]->size+1;
}
void node :: push_down()
{
if(tur)
{
if(c[0]!=null) c[0]->reverse();
if(c[1]!=null) c[1]->reverse();
tur=0;
}
}
node *build(int l,int r)
{
if(l>r)return null;
int mid=l+r>>1;
node *re=new node(); re->val=a[mid];
re->c[0]=build(l,mid-1); re->c[1]=build(mid+1,r);
re->c[0]->fa=re;re->c[1]->fa=re;
re->push_up();
return re;
}
void initialize()
{
root=new node();
root->c[1]=new node();root->c[1]->fa=root;
}
void Free(node *x)
{
if(x==null) return ;
Free(x->c[0]);
Free(x->c[1]);
free(x);
}
void rotate(node *x)
{
node *y=x->fa;int l=(x!=y->c[0]),r=l^1;
y->c[l]=x->c[r];x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(y==y->fa->c[r]) y->fa->c[r]=x;
else y->fa->c[l]=x;
y->fa=x; y->push_up();x->push_up();
if(root==y) root=x;
}
void splay(node *x,node *tar)
{
while(x!=tar)
{
node *y=x->fa,*z=y->fa;
if(y==tar) break;
if(z==tar) {rotate(x);break;}
if((y!=z->c[0])^(x==y->c[0])) rotate(y);
else rotate(x);
rotate(x);
}
}
void find(node *x,int y,node *z)
{
while(1)
{
x->push_down();
int tmp=x->c[0]->size;
if(y<=tmp) x=x->c[0];
else
{
y-=tmp;if(y==1) break;y--;
x=x->c[1];
}
}
splay(x,z);
}
void dfs(node *x)
{
if(x==null) return ;
x->push_down();
dfs(x->c[0]);
printf("%c",x->val);
dfs(x->c[1]);
}
int main()
{
scanf("%d",&m);
initialize();
//dfs(root);
//puts("");
while(m--)
{
scanf("%s",st);
switch(st[0])
{
case 'I':
{
int len;
scanf("%d",&len);
find(root,now+1,null);
find(root,now+2,root);
ch=getchar();
while(ch<32||ch>126) ch=getchar();
a[1]=ch;
for(int i=2;i<=len;i++) a[i]=getchar();
root->c[1]->c[0]=build(1,len);
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->push_up();
root->push_up();
break;
}
case 'M':
{
scanf("%d",&n);
now=n;
break;
}
case 'D':
{
scanf("%d",&n);
find(root,now+1,null);
find(root,now+n+2,root);
node *tmp=root->c[1]->c[0];
root->c[1]->c[0]=null;
root->c[1]->push_up();
root->push_up();
Free(tmp);
break;
}
case 'R':
{
scanf("%d",&n);
find(root,now+1,null);
find(root,now+n+2,root);
root->c[1]->c[0]->reverse();
root->c[1]->push_up();
root->push_up();
break;
}
case 'G':
{
find(root,now+1,null);
find(root,now+3,root);
printf("%c\n",root->c[1]->c[0]->val);
break;
}
case 'P':now--;break;
case 'N':now++;break;
}
//printf("%d\n",now);
//dfs(root);
//puts("");
}
return 0;
}#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int m,n,now;
char st[1000],a[3001000],ch;
struct node
{
node *fa,*c[2];
char val;
int size;
node();
void push_up();
}*null=new node(),*root;
node :: node()
{
fa=c[0]=c[1]=null;
size=null?1:0;
val=1;
}
void node :: push_up()
{
size=c[0]->size+c[1]->size+1;
}
node* build(int l,int r)
{
if(l>r)return null;
int mid=l+r>>1;
node *re=new node(); re->val=a[mid];
re->c[0]=build(l,mid-1); re->c[1]=build(mid+1,r);
re->c[0]->fa=re; re->c[1]->fa=re;
re->push_up();
return re;
}
void initialize()
{
root=new node();
root->c[1]=new node();
root->c[1]->fa=root;
root->c[1]->push_up();root->push_up();
}
void Free(node *x)
{
if(x==null) return ;
Free(x->c[0]);
Free(x->c[1]);
free(x);
}
void rotate(node *x)
{
node *y=x->fa;int l=(x!=y->c[0]),r=l^1;
y->c[l]=x->c[r];x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(y==y->fa->c[r]) y->fa->c[r]=x;
else if(y==y->fa->c[l]) y->fa->c[l]=x;
y->fa=x; y->push_up();x->push_up();
if(y==root) root=x;
}
void splay(node *x,node *tar)
{
while(x!=tar)
{
node *y=x->fa,*z=y->fa;
if(y==tar) break;
if(z==tar) {rotate(x);break;}
if((y==z->c[0])^(x==y->c[0])==0) rotate(y);
else rotate(x);
rotate(x);
}
}
void find(node *x,int y,node *z)
{
while(1)
{
int tmp=x->c[0]->size;
if(y<=tmp) x=x->c[0];
else
{
y-=(tmp+1);
if(!y) break;
x=x->c[1];
}
}
splay(x,z);
}
void rd(int x)
{
int cnt=1;char ch;
while(cnt<=x)
{
ch=getchar();
if(ch!='\n')
a[cnt]=ch,cnt++;
}
}
void dfs(node *x)
{
if(x==null) return ;
dfs(x->c[0]);
printf("%c",x->val);
dfs(x->c[1]);
}
int main()
{
scanf("%d",&m);
initialize();
while(m--)
{
scanf("%s",st);
switch(st[0])
{
case 'I':
{
int len; scanf("%d",&len); rd(len);
find(root,now+1,null);
find(root,now+2,root);
root->c[1]->c[0]=build(1,len);
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->push_up();
root->push_up();
break;
}
case 'M':scanf("%d",&now);break;
case 'D':
{
scanf("%d",&n);
find(root,now+1,null);
find(root,now+n+2,root);
node *tmp=root->c[1]->c[0];
root->c[1]->c[0]=null;
root->c[1]->push_up();
root->push_up();
Free(tmp);
break;
}
case 'G':
{
scanf("%d",&n);
find(root,now+1,null);
find(root,now+n+2,root);
dfs(root->c[1]->c[0]);
puts("");
break;
}
case 'P':now--;break;
case 'N':now++;break;
}
}
return 0;
}