BZOJ 1269: [AHOI2006]文本编辑器editor Splay-白红宇

BZOJ 1269: [AHOI2006]文本编辑器editor Splay

阅读量：5275 次

发布时间：2019-06-14

本文共 2987 字，大约阅读时间需要 9 分钟。

Notice:祝大家新年快乐！

1269: [AHOI2006]文本编辑器editor

Time Limit: 10 Sec

Memory Limit: 162 MB

Submit: 921

Solved: 320

[ ][ ][ ]

Description

这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义：文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。编写一个程序： 建立一个空的文本编辑器。 从输入文件中读入一些操作指令并执行。 对所有执行过的GET操作，将指定的内容写入输出文件。

Input

输入文件中第一行是指令条数N，以下是需要执行的N个操作。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。

Output

依次对应输入文件中每条GET指令的输出，不得有任何多余的字符。

Sample Input

Insert 13

Balanced eert

Move 2

Delete 5

Insert 7

editor

Move 0

Get

Move 11

Rotate 4

Get

Sample Output

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

[ ][ ][ ]

分析：splay的基本操作。

1.插入，我们需要把插入的位置伸展到根，然后再把伸展之后的后一个位置伸展到根的右儿子，插入就直接把所有的数插入到根的右儿子的左子树中。

2.删除，我们把需要删除的整个区间[a,b]直接伸展到根的右儿子的左子树，即把a-1伸展到根，把b+1伸展到根的右儿子，然后把根的右儿子的左子树整个删除掉即可

3.旋转，lazy标记，每当我们往下遍历的时候，需要把lazy标记下沉。而旋转过程中，比如我们需要对区间[a,b]旋转，我们可以把a-1旋转到根，把b+1旋转到根的右儿子，然后把根的右儿子的左子树的标记翻转一下就行了。

4.输出，我们需要输出光标后的第一个字符，我们可以直接把光标的位置伸展到根，然后再求根的右儿子的最小值输出

5.移动到第k个字符后面，我们直接把光标改变，无需把该位置伸展到根，只需要用的时候再进行伸展操作

6.前移（后移），直接把光标减一（加一），无需进行伸展操作

对于这题来说，插入的时候需要把插入的字符串递归构造一个成一个perfect tree来插入。

#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;typedef long long ll;typedef unsigned long long ull;#define debug puts("here")#define rep(i,n) for(int i=0;i
                
                 r) return; int mid = (l+r)>>1; new_node(x,y,s[mid]); build(lx,l,mid-1,x,s); build(rx,mid+1,r,x,s); update(x); } inline void setc(int y,int d,int x){ ch[y][d] = x; pre[x] = y; } inline int sgn(int x){ return ch[px][1]==x; } inline void _rot(int x,int d){ int y = px; int z = py; push_down(y); push_down(x); setc(y,!d,ch[x][d]); if(z) setc(z,sgn(y),x); pre[x] = z; setc(x,d,y); update(y); } inline void rot(int x){_rot(x,!sgn(x));} inline void zag(int x){_rot(x,0);} inline void zig(int x){_rot(x,1);} inline int splay(int x,int goal=0){ push_down(x); while(px!=goal){ int y = px; int z = py; if(z==goal){ rot(x); break; } if(lz==y){ if(ly==x) zig(y),zig(x); else zag(x),zig(x); } else{ if(ry==x) zag(y),zag(x); else zig(x),zag(x); } } update(x); if(goal==0) root = x; return x; } inline int get_Kth(int x,int k){ push_down(x); int tmp = sz[lx]+1; if(tmp==k) return x; if(k
                 
                  >ncase; init(); while(ncase--){ scanf("%s",op); switch(op[0]){ case 'M':Move();break; case 'I':Insert();break; case 'D':Delete();break; case 'R':Rotate();break; case 'G':Get();break; case 'P':Prev();break; default:Next(); } } return 0;}

转载于:https://www.cnblogs.com/yejinru/archive/2013/02/10/2909797.html

你可能感兴趣的文章