1269: [AHOI2006]文本编辑器editor
Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2540 Solved: 923 [Submit][Status][Discuss] 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操作不会把光标移动到非法位置。 输入文件没有错误。
模板题：
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;struct Node{Node *ch[2];int r,s;char v;bool f;Node(char v):v(v) {ch[0]=ch[1]=NULL; r=rand(); s=1; f=false;}void update(){s=1;if(ch[0]!=NULL) s+=ch[0]->s;if(ch[1]!=NULL) s+=ch[1]->s;}void pushdown(){if(f){if(ch[0]!=NULL) ch[0]->f=!ch[0]->f;if(ch[1]!=NULL) ch[1]->f=!ch[1]->f;swap(ch[0],ch[1]);f=false;}}}*root;int n;char ch[10];Node *merge(Node* &x,Node* &y){if(x==NULL) return y;if(y==NULL) return x;if(x->r < y->r){if(x!=NULL) x->pushdown();x->ch[1]=merge(x->ch[1],y);if(x!=NULL) x->update();return x;}else{if(y!=NULL) y->pushdown();y->ch[0]=merge(x,y->ch[0]);if(y!=NULL) y->update();return y;}}void split(Node* &o,Node* &x,Node* &y,int now){if(o==NULL){x=y=NULL;return ;}if(now==0){x=NULL;y=o;return ;}if(now==o->s){x=o;y=NULL;return ;}o->pushdown();if((o->ch[0]==NULL? 0: o->ch[0]->s)>=now){split(o->ch[0],x,y,now);o->ch[0]=y;o->update();y=o;}else{split(o->ch[1],x,y,now-(o->ch[0]==NULL? 0: o->ch[0]->s)-1);o->ch[1]=x;o->update();x=o;}}void insert(Node* &o,){int i;Node *a,*b,*c;char ss;split(o,a,b,now);for(i=1;i<=len;++i){while(1){scanf(“%c”,&ss);if(ss>=32&&ss<=126) break;}c=new Node(ss);a=merge(a,c);}o=merge(a,b);}void del(Node* &o,){Node *a,*b,*c,*d;split(o,a,b,now);split(b,c,d,len);o=merge(a,d);}void rotate(Node* &o,){Node *a,*b,*c,*d;split(o,a,b,now);split(b,c,d,len);if(c!=NULL) c->f=!c->f;b=merge(c,d);o=merge(a,b);}void print(Node* &o,int now){Node *a,*b,*c,*d;split(o,a,b,now);split(b,c,d,1);printf(“%c\n”,c->v);b=merge(c,d);o=merge(a,b);}int main(){int now=0,len;scanf(“%d”,&n);while(n–){scanf(“%*c%s”,&ch);if(ch[0]==’M’) scanf(“%d”,&now);if(ch[0]==’I’){scanf(“%d”,&len);insert(root,now,len);}if(ch[0]==’D’){scanf(“%d”,&len);del(root,now,len);}if(ch[0]==’R’){scanf(“%d”,&len);rotate(root,now,len);}(ch[0]==’N’) now+=1;}}1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB Submit: 8948 Solved: 2691 [Submit][Status][Discuss] Description
Input
输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
HINT
世上没有绝望的处境，只有对处境绝望的人。
