这题写了我1.5h……
以后写题目必须认真、仔细!
Pushdown居然写错了……调试了半天
所以以后必须仔细想好细节再写,这样才能节省时间。
#include<cstdio> #include<algorithm> using namespace std; int n,move_to=0; char s[2000005]; struct Node{ char v; int rev,siz; Node *ch[2],*fa; Node(char ch,Node *fat); void Pushdown(); void Pushup(); }*root,*Null; Node::Node(char c,Node *fat=Null){ ch[0]=ch[1]=Null; fa=fat; siz=1; rev=0; v=c; } void Node::Pushdown(){ if(rev){ rev=0; if(ch[0]!=Null)ch[0]->rev^=1; if(ch[1]!=Null)ch[1]->rev^=1; swap(ch[0]->ch[0],ch[0]->ch[1]); swap(ch[1]->ch[0],ch[1]->ch[1]); } } void Node::Pushup(){ siz=1; if(ch[0]!=Null)siz+=ch[0]->siz; if(ch[1]!=Null)siz+=ch[1]->siz; } void Rotate(Node *x,int kind){ Node *y=x->fa,*z=y->fa; y->ch[!kind]=x->ch[kind]; if(x->ch[kind]!=Null)x->ch[kind]->fa=y; x->fa=z; if(z!=Null)z->ch[z->ch[1]==y]=x; y->fa=x; x->ch[kind]=y; y->Pushup(); x->Pushup(); } void Splay(Node *x,Node *place){ while(x->fa!=place){ Node *y=x->fa,*z=y->fa; if(z==Null || z==place)Rotate(x,y->ch[0]==x); else { if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);} else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);} else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);} else {Rotate(y,1);Rotate(x,1);} } } if(place==Null)root=x; } Node *Find(Node *splay,int k){ splay->Pushdown(); if(k==splay->ch[0]->siz+1)return splay; if(k<=splay->ch[0]->siz)return Find(splay->ch[0],k); return Find(splay->ch[1],k-1-splay->ch[0]->siz); } Node *Split(int pos,int tot){ Node *x=Find(root,pos),*y=Find(root,pos+tot+1); Splay(x,Null); Splay(y,root); return y->ch[0]; } Node *Build(int l,int r){ if(l>r)return Null; int mid=l+r>>1; Node *splay=new Node(s[mid],Null); splay->ch[0]=Build(l,mid-1); if(splay->ch[0]!=Null)splay->ch[0]->fa=splay; splay->ch[1]=Build(mid+1,r); if(splay->ch[1]!=Null)splay->ch[1]->fa=splay; splay->Pushup(); return splay; } void Del_Tree(Node *splay){ if(splay==Null)return; splay->Pushdown(); Del_Tree(splay->ch[0]); Del_Tree(splay->ch[1]); if(splay->ch[0]!=Null)delete splay->ch[0]; if(splay->ch[1]!=Null)delete splay->ch[1]; splay->ch[0]=Null; splay->ch[1]=Null; splay->Pushup(); } Node *GetNull(){ Node *p=new Node('#',Null); p->ch[0]=p->ch[1]=p->fa=p; p->siz=p->rev=0; } void Build_First(){ Null=GetNull(); s[1]='H'; s[2]='i'; root=Build(1,2); } void Insert(int pos,int tot){ Node *x=Find(root,pos+1),*y=Find(root,pos+2); Splay(x,Null);Splay(y,root); y->ch[0]=Build(1,tot); if(y->ch[0]!=Null)y->ch[0]->fa=y; y->Pushup(); x->Pushup(); } void Delete(int pos,int tot){ Node *seq=Split(pos,tot),*fat=seq->fa; Del_Tree(seq); if(seq!=Null)delete seq; fat->ch[0]=Null; fat->Pushup(); fat->fa->Pushup(); } void Reverse(int pos,int tot){ Node *seq=Split(pos,tot),*fat=seq->fa; seq->rev^=1; swap(seq->ch[0],seq->ch[1]); fat->Pushup(); fat->fa->Pushup(); } char GetKey(int pos){ Node *u=Split(pos,1); return u->v; } void GetString(int len){ char ch; while((ch=getchar())=='\n'); s[1]=ch; for(int i=2;i<=len;i++){s[i]=getchar();} s[len+1]='\0'; } int main(){ freopen("1269.in","r",stdin); freopen("1269.out","w",stdout); scanf("%d",&n); Build_First(); for(int i=1;i<=n;i++){ char opt[10]; scanf("%s",opt); if(opt[0]=='M'){ int k; scanf("%d",&k); move_to=k; } if(opt[0]=='I'){ int tot; scanf("%d",&tot); GetString(tot); Insert(move_to,tot); } if(opt[0]=='D'){ int tot; scanf("%d",&tot); Delete(move_to+1,tot); } if(opt[0]=='R'){ int tot; scanf("%d",&tot); Reverse(move_to+1,tot); } if(opt[0]=='G'){ printf("%c\n",GetKey(move_to+1)); } if(opt[0]=='P')move_to--; if(opt[0]=='N')move_to++; } return 0; }