splay 读入坑爹

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define clr(a,x) memset(a,x,sizeof(a)) 9 #define rep(i,l,r) for(int i=l;i<(r);i++) 10 using namespace std; 11 typedef long long ll; 12 const int maxn=2000009; 13 int n,now=0; 14 char a[maxn]; 15 struct node*null,*root; 16 struct node{ 17 int s; 18 char c; 19 node*ch[2]; 20 bool rev; 21 node(){ 22 s=0;c=rev=0;ch[0]=ch[1]=null; 23 } 24 inline int cmp(int k){ 25 k-=ch[0]->s; 26 if(k==1) return -1; 27 return k<=0?0:1; 28 } 29 inline void maintain(){ 30 s=ch[0]->s+ch[1]->s+1; 31 } 32 inline void Rev(){ 33 rev^=1; 34 swap(ch[0],ch[1]); 35 } 36 inline void pushdown(){ 37 if(rev){ 38 if(ch[0]!=null) ch[0]->Rev(); 39 if(ch[1]!=null) ch[1]->Rev(); 40 rev=0; 41 } 42 } 43 }; 44 inline void rot(node*&o,int d){ 45 o->pushdown(); 46 node*p=o->ch[d^1]; 47 p->pushdown(); 48 o->ch[d^1]=p->ch[d];p->ch[d]=o; 49 o->maintain();p->maintain(); 50 o=p; 51 } 52 inline void splay(node*&o,int k){ 53 o->pushdown(); 54 int d=o->cmp(k);//cout<
             
              ch[0]->s<
              
               ch[0]->s+1; 57 node*p=o->ch[d]; 58 p->pushdown(); 59 int d1=p->cmp(k); 60 int k1=(d1)?k-p->ch[0]->s-1:k; 61 if(d1!=-1){ 62 splay(p->ch[d1],k1); 63 d==d1?rot(o,d^1):rot(o->ch[d],d); 64 } 65 rot(o,d^1); 66 } 67 struct queue{ 68 int fron,rear,cnt; 69 node*x[maxn<<1]; 70 queue(){ 71 fron=0;rear=0; 72 } 73 inline void push(node*o){ 74 x[rear++]=o; 75 } 76 inline node*front(){ 77 return x[fron]; 78 } 79 inline void pop(){ 80 fron++; 81 } 82 }; 83 queue Q; 84 node*newnode(char ch){ 85 node*o=Q.front();Q.pop(); 86 o->ch[0]=o->ch[1]=null; 87 o->s=1;o->rev=0; 88 o->c=ch; 89 return o; 90 } 91 node*build(int l,int r){ 92 if(l>=r) return null; 93 int mid=(l+r)>>1; 94 node*o=newnode(a[mid]); 95 if(l
               
                ch[0]=build(l,mid); 96 if(r>mid+1) o->ch[1]=build(mid+1,r); 97 o->maintain(); 98 return o; 99 }100 node x[maxn];101 void init(){102 a[1]='$';a[2]='$';103 rep(i,0,maxn) Q.push(x+i);104 null=newnode(0);105 null->s=0;106 root=build(1,3);107 }108 #define ok(c) (c>=32&&c<=126)109 void read(int l){110 int cnt=0;111 char ch=getchar();112 while(!ok(ch)) ch=getchar();113 while(cnt
                
                 ch[0]);123 Q.push(o);124 del(o->ch[1]);125 }126 void dfs(node*o){127 if(o==null) return;128 o->pushdown();129 dfs(o->ch[0]);130 putchar(o->c);131 dfs(o->ch[1]);132 }133 int main(){134 //freopen("test.in","r",stdin);135 //freopen("test.out","w",stdout);136 scanf("%d",&n);137 init();138 while(n--){139 // dfs(root);140 // putchar('\n');141 int len;142 char opt[20];143 scanf(" %s",opt);144 if(opt[0]=='M') scanf("%d",&now);145 else if(opt[0]=='I'){146 scanf("%d",&len);read(len);147 splay(root,now+1);splay(root->ch[1],now-root->ch[0]->s+1);148 root->ch[1]->ch[0]=build(1,len+1);149 root->maintain();root->ch[1]->maintain();150 }else if(opt[0]=='D'){151 scanf("%d",&len);152 splay(root,now+1);splay(root->ch[1],now-root->ch[0]->s+len+1);153 del(root->ch[1]->ch[0]);root->ch[1]->ch[0]=null;154 root->maintain();root->ch[1]->maintain();155 }else if(opt[0]=='R'){156 scanf("%d",&len);157 splay(root,now+1);splay(root->ch[1],now-root->ch[0]->s+len+1);158 root->ch[1]->ch[0]->Rev();159 }else if(opt[0]=='G'){160 splay(root,now+2);161 putchar(root->c);putchar('\n');162 //putchar(root->c);163 }else if(opt[0]=='P') now--;164 else if(opt[0]=='N') now++;165 //cout<
                 
                  <<" ok\n";166 }167 //fclose(stdin);168 //fclose(stdout);169 return 0;170 }
                 
                
               
              
             
            
           
          
         
        
       
      

1269: [AHOI2006]文本编辑器editor

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 2588  Solved: 950

[][][]

Description

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

Input

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

Output

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

Sample Input

10

Insert 13

Balanced eert

Move 2

Delete 5

Next

Insert 7

editor

Move 0

Get

Move 11

Rotate 4

Get

Sample Output

B

t

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

[ ][ ][ ]