设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

BZOJ 1269 [AHOI2006]文本编辑器editor Splay伸展树

2014-09-13 20:00:00.0 BZOJ BZOJ BZOJ1269 Splay 伸展树 AHOI2006  
导读:本文jiangyuze831给大家介绍 BZOJ 1269 [AHOI2006]文本编辑器editor Splay伸展树。题目大意:类似于我们正常输入文本,现在模拟这样的一个功能。它支持:1.将光标移动到第k个字符前2.在光标后面加入长度为l。。。

题目大意:类似于我们正常输入文本,现在模拟这样的一个功能。它支持:

1.将光标移动到第k个字符前

2.在光标后面加入长度为l的字符串

3.删除光标后面l个字符

4.将光标后面l个字符翻转

5.输出光标后面的字符,并保持光标位置不变

6.将光标向前移动一个位置

7.将光标向后移动一个位置

注意:如下图所示,两次RE,得来的教训是插入的字符串长度要开到10000010-_-#


还有BZOJ坑爹啊,不知道什么原理,字符串总处理不明白,据说是样例里面有\r。反正遇到不太对劲就多getchar()几下就好了,\r\n傻傻分不清楚。。


CODE:


#include #include #include #include using namespace std;struct Complex{ char val; int size; bool reverse; Complex *son[2],*father; bool Check() {  return father->son[1] == this; } void Combine(Complex *a,bool dir) {  son[dir] = a;  a->father = this; } void Reverse() {  reverse ^= 1;  swap(son[0],son[1]); }}none,n,*nil = &none,*root = &n;Complex *Kth(Complex *a,int k);Complex *BuildTree(int l,int r,Complex *f);inline Complex *NewComplex(Complex *father,char x);inline void Pretreatment();inline void SplaySeg(int x,int y);inline void Rotate(Complex *a,bool dir);inline void Splay(Complex *a,Complex *aim);inline void PushDown(Complex *a);inline void PushUp(Complex *a);void Gets(char *s);int cnt;int position;char s[10000010];int main(){ Pretreatment(); cin >> cnt; for(int x,i = 1;i <= cnt; ++i) {  scanf("%s",s);  switch(s[0]) {   case 'M':    scanf("%d",&x);    position = x;    break;   case 'I': {    char c;    scanf("%d%c",&x,&c);    Gets(s + 1);    SplaySeg(position,position);                Complex *temp = BuildTree(1,(int)strlen(s + 1),root->son[1]);                root->son[1]->Combine(temp,false);    PushUp(root->son[1]),PushUp(root);    break;   }   case 'D':    scanf("%d",&x);    SplaySeg(position,position + x);    root->son[1]->son[0]->father = nil;    root->son[1]->son[0] = nil;    PushUp(root->son[1]),PushUp(root);    break;   case 'R':    scanf("%d",&x);    SplaySeg(position,position + x);    root->son[1]->son[0]->Reverse();    break;   case 'G':    Splay(Kth(root,position + 2),nil);    putchar(root->val),puts("");    break;   case 'P':position--; break;   case 'N':position++; break;  } } return 0;}inline void Pretreatment(){ nil->father = nil; nil->son[0] = nil->son[1] = nil; nil->size = 0; nil->reverse = false; root->size = 2,root->val = '#'; root->Combine(NewComplex(root,'#'),true); root->son[0] = root->father = nil;}inline Complex *NewComplex(Complex *f,char x){ Complex *re = new Complex(); re->father = f; re->son[0] = re->son[1] = nil; re->val = x; re->size = 1; re->reverse = false; return re;}inline void Rotate(Complex *a,bool dir){ Complex *f = a->father; PushDown(f),PushDown(a); f->son[!dir] = a->son[dir]; f->son[!dir]->father = f; a->son[dir] = f; a->father = f->father; f->father->son[f->Check()] = a; f->father = a; PushUp(f); if(root == f) root = a;}inline void Splay(Complex *a,Complex *aim){ while(a->father != aim) {  if(a->father->father == aim)   Rotate(a,!a->Check());  else if(!a->father->Check()) {   if(!a->Check())    Rotate(a->father,true),Rotate(a,true);   else Rotate(a,false),Rotate(a,true);  }  else {   if(a->Check())    Rotate(a->father,false),Rotate(a,false);   else Rotate(a,true),Rotate(a,false);  } } PushUp(a);}Complex *Kth(Complex *a,int k){ PushDown(a); if(k <= a->son[0]->size)  return Kth(a->son[0],k); k -= a->son[0]->size; if(k == 1) return a; return Kth(a->son[1],k - 1);}Complex *BuildTree(int l,int r,Complex *f){ if(l > r) return nil; int mid = (l + r) >> 1; Complex *re = NewComplex(f,s[mid]); re->Combine(BuildTree(l,mid - 1,re),false); re->Combine(BuildTree(mid + 1,r,re),true); PushUp(re); return re;}inline void PushDown(Complex *a){ if(a == nil) return ; if(a->reverse) {  if(a->son[0] != nil)   a->son[0]->Reverse();  if(a->son[1] != nil)   a->son[1]->Reverse();  a->reverse = false; }}inline void PushUp(Complex *a){ if(a == nil) return ; a->size = a->son[0]->size + a->son[1]->size + 1;} inline void SplaySeg(int x,int y){ Splay(Kth(root,x + 1),nil); Splay(Kth(root,y + 2),root);}void Gets(char *s){ char c; while(c = getchar(),c != '\n')  *s++ = c; *s = '\0';}


(编辑: jiangyuze831)

网友评论
相关文章