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

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

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

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

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

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

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

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

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

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

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

vcD4KPHA+u7nT0EJaT0q/07X5sKGjrLK71qq1wMqyw7TUrcDto6zX1rf7tK7X3LSmwO2yu8P3sNejrL7dy7XKx9H5wP3A78Pm09BccqGjt7TV/dP2tb2yu8yrttS+or7NtuBnZXRjaGFyKCm8uM/Cvs26w8HLo6xcclxuybXJtbfWsrvH5bP+oaOhozwvcD4KPHA+PGJyPgo8L3A+CjxwPkNPREWjujwvcD4KPHA+PGJyPgo8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#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 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 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 = ''; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:[LeetCode]Longest Valid Parentheses
下一篇:HDU 5000 Clone(瞎搞)
相关文章

BZOJ 1269 文本编辑器 Splay

bzoj 1269 文本编辑器editor splay

基本的HTML文本解析器的设计和实现(C

c++实现文本中英文单词和汉字字符的统

QTextEdit限制文本长度

QString 文本长度判断

C++ Primer 学习笔记_74_面向对象编

C++ Primer 学习笔记_73_面向对象编

C++ - 同步读写文本 代码(C++)

C++ - 删除文本的最后一行 代码(C++)

图文推荐

BZOJ 1269 [AHOI2006]文本编辑器editor Splay伸展树
ZOJ 3640 Help Me
BZOJ 1269 [AHOI2006]文本编辑器editor Splay伸展树
CF 518C(Anya and
BZOJ 1269 [AHOI2006]文本编辑器editor Splay伸展树
hdu 1016 Prime R
UVA - 11987 - A
分类:默认分类 时间:2015-03-04 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.026 (s). 10 q(s)