After trying to solve problem EDIT1(Editor) and being ****ed by Brainf**k, Blue Mary decided to set another difficult problem about editor.
Some definations:
Editor is a structure.It contains one text and one cursor.The operations are listed below:
-------------------------------------------------------------------------- | Name | Input format | function | -------------------------------------------------------------------------- | Move(k) | Move k | Move the cursor after the kth character | | | | in the text. If k=0, you should put | | | | the cursor at the start of the text. | -------------------------------------------------------------------------- | Insert(n,s) | Insert n s | Insert string s whose length is n(>=1) | | | | after the cursor.The cursor doesn‘t move. | -------------------------------------------------------------------------- | Delete(n) | Delete n | Delete n(>=1) characters after the cursor.| | | | The cursor doesn‘t move. | -------------------------------------------------------------------------- | Get(n) | Get n | Output n(>=1) characters after the cursor.| -------------------------------------------------------------------------- | Prev() | Prev | Move the cursor one character forward. | -------------------------------------------------------------------------- | Next() | Next | Move the cursor one character backward. | --------------------------------------------------------------------------
If the text of a editor is empty,we say the editor is empty.
Here is an example._ denotes to the cursor,$ denotes to the start and the end.At start the editor is empty.
------------------------------------------------------------------------------ | Operation | Text after the operation | Output | ------------------------------------------------------------------------------ | INSERT(13,"Balanced tree") | $_Balanced tree$ | $$ | ------------------------------------------------------------------------------ | MOVE(2) | $Ba_lanced tree$ | $$ | ------------------------------------------------------------------------------ | DELETE(5) | $Ba_d tree$ | $$ | ------------------------------------------------------------------------------ | NEXT() | $Bad_ tree$ | $$ | ------------------------------------------------------------------------------ | INSERT(7," editor") | $Bad_ editor tree$ | $$ | ------------------------------------------------------------------------------ | MOVE(0) | $_Bad editor tree$ | $$ | ------------------------------------------------------------------------------ | GET(15) | $_Bad editor tree$ | $Bad editor tree$ | ------------------------------------------------------------------------------
Your task is:
the very first line contains the number of testcases T(T<=4).T tests follow.
For each test, the first line is the number of operations N.N operations follow.
Blue Mary is so depressed with the problem EDIT1 that she decides to make the problem more difficult.So she inserts many extra line breaks in the string of the Insert operation.You must ignore them.
Except line breaks, all the charaters‘ ASCII code are in [32,126]. There‘s no extra space at the end of a line.
You can assume that for each test case:
The output should contain T blocks corresponding to each testcase.
For each test case, the output should contain as many lines as the get operations in the input.Each line should contains the output of each get operation.
Input: 1 15 Insert 26 abcdefghijklmnop qrstuv wxy Move 15 Delete 11 Move 5 Insert 1 ^ Next Insert 1 _ Next Next Insert 4 .\/. Get 4 Prev Insert 1 ^ Move 0 Get 22 Output: .\/. abcde^_^f.\/.ghijklmno
Warning: large Input/Output data, be careful with certain languages
Blue Mary‘s note: the test case #1 has something wrong and it has been fixed on April 27th, 2007.Solutions has been rejudged. Please accept my apology.
题目取自SPOJ
几点注意的：
1、bzoj样例有误。
2、Insert操作如果读入长度用scanf("%d\n",&x)读，会自动过滤下一行空格，导致Wa90.
相信这是我写过最差的程序了。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<cstdlib> using namespace std; #define MAXN MAXT #define MAXT 1024*1024*4+1000 int n,m; struct Splay_tree { struct node { node *ch[2],*fa; char w; int siz; }; node E[MAXN],nil_node; queue<node* > Q; node *root,*nil; Splay_tree() { int i; for (i=1;i<MAXT;i++) { Q.push(&E[i]); } nil_node.ch[0]=nil_node.ch[1]=NULL; nil_node.w=‘#‘; nil_node.siz=0; nil=&nil_node; root=nil; root->fa=nil; } void update(node *now) { if (now==nil)throw "illegal update"; now->siz=now->ch[0]->siz+now->ch[1]->siz+1; } void rotate(node *now,int p)//注意不要改变nil的值,now的祖父节点或儿子节点可能为nil { node *pnt=now->fa; now->fa=pnt->fa; if (pnt->fa!=nil) { if (pnt->fa->ch[0]==pnt) { pnt->fa->ch[0]=now; }else { pnt->fa->ch[1]=now; } } pnt->fa=now; pnt->ch[p^1]=now->ch[p]; if (now->ch[p]!=nil)now->ch[p]->fa=pnt; now->ch[p]=pnt; update(pnt);//注意顺序 update(now); } void splay(node *now,node *top) { node *pnt; if (now==top)return ; while (now->fa!=top) { pnt=now->fa; if (pnt->ch[0]==now) { if (pnt->fa!=top&&pnt->fa->ch[0]==pnt) { rotate(pnt,1); } rotate(now,1); }else { if (pnt->fa!=top&&pnt->fa->ch[1]==pnt) { rotate(pnt,0); } rotate(now,0); } } if (top==nil) { root=now; } } node *get_node(int rank) { node *now=root; if (now->siz<rank)throw "Not enough node"; while (true) { if (now->ch[0]->siz+1==rank) { return now; } if (now->ch[0]->siz+1<rank) { rank-=now->ch[0]->siz+1; now=now->ch[1]; }else { now=now->ch[0]; } } return now; } node *get_min_node(node *now) { if (now==nil)throw "illegal call"; //if (now==nil)return nil; while (now->ch[0]!=nil) { now=now->ch[0]; } return now; } pair<node*,node*> split(int pos) { if (pos==0)return make_pair(nil,root); splay(get_node(pos),nil); pair<node*,node*> ret; ret.first=root; ret.second=root->ch[1]; root->ch[1]->fa=nil; root->ch[1]=nil; update(root); root=NULL; return ret; } node * merge(node * a1,node *a2) { if (a1==nil)return a2; if (a2==nil)return a1; root=a2; splay(get_min_node(a2),nil); root->ch[0]=a1; a1->fa=root; update(root); return root; } void insert(int pos,char ch)//插入ch后前面有pos个字符 { node *now=Q.front(); Q.pop(); now->w=ch; if (pos==0) { if (root==nil) { now->fa=nil; now->ch[0]=now->ch[1]=nil; now->siz=1; root=now; return ; } splay(get_min_node(root),nil); now->fa=root; root->ch[0]=now; now->ch[0]=now->ch[1]=nil; update(now); update(root); return ; } splay(get_node(pos),nil); if (root->ch[1]!=nil)splay(get_min_node(root->ch[1]),root); now->fa=root; now->ch[1]=root->ch[1]; root->ch[1]->fa=now; root->ch[1]=now; now->ch[0]=nil; update(now); update(root); splay(now,nil); return ; } void insert2(int pos,char* str,int len) { if (len==0)return ; pair<node*,node*> pr1; pr1=split(pos); //scan(pr1.first);cout<<endl; //scan(pr1.second);cout<<endl; node *now=build_tree(str,0,len-1,nil); root=merge(pr1.first,merge(now,pr1.second)); } node *build_tree(char *str,int l,int r,node *fa) { if (l>r)return nil; node *now=Q.front(); int mid=(l+r)/2; Q.pop(); now->fa=fa; now->w=str[mid]; now->ch[0]=build_tree(str,l,mid-1,now); now->ch[1]=build_tree(str,mid+1,r,now); update(now); return now; } void recycle(node *now) { if (now==nil)return ; if (now->fa!=nil) { if (now==now->fa->ch[0]) { now->fa->ch[0]=nil; }else if (now==now->fa->ch[1]) { now->fa->ch[1]=nil; } } recycle(now->ch[0]); recycle(now->ch[1]); Q.push(now); } void erase(int pos,int len) { pair<node*,node *> pr1,pr2; pr1=split(pos); root=pr1.second; pr2=split(len); recycle(pr2.first); root=merge(pr1.first,pr2.second); } void scan(node *now) { if (now==nil)return; if (now->siz!=now->ch[0]->siz+now->ch[1]->siz+1) { throw "Size error"; } if (now->ch[0]!=nil&&now->ch[0]->fa!=now)throw "Wrong ptr"; if (now->ch[1]!=nil&&now->ch[1]->fa!=now)throw "Wrong ptr"; scan(now->ch[0]); printf("%c",now->w); scan(now->ch[1]); } void scan2(node *now) { if (now==nil)return; scan2(now->ch[0]); printf("%c",now->w); scan2(now->ch[1]); } void print_str(int pos,int len) { if (!len){puts("");return ;}/**/ if (pos==0) { if (len==root->siz) { scan(root); puts(""); return ; } splay(get_node(len+1),nil); scan(root->ch[0]); puts(""); return ; } splay(get_node(pos),nil); if (pos+len<=root->siz)splay(get_node(pos+len),root); node *temp=root->ch[0],*temp2=root->ch[1]->ch[1]; root->ch[0]=nil;root->ch[1]->ch[1]=nil; scan2(root->ch[1]);puts(""); root->ch[0]=temp;root->ch[1]->ch[1]=temp2; return ; } }spt; int i; char str1[MAXN]; int main() { //freopen("editor2.in","r",stdin); //freopen("out2.txt","w",stdout); try { int j,k,x,y; scanf("%d",&n); char od[10]; int m,p; char *ptr; char ch; int nowad=0; int root2; for (i=0;i<n;i++) { scanf("%s ",od); switch (od[0]) { case ‘M‘: scanf("%d\n",&x); nowad=x; break; case ‘I‘: scanf("%d",&x); getchar(); for (j=0;j<x;j++) { ch=getchar(); if (ch<32||ch>126) { j--; continue; } str1[j]=ch; //if (i!=1)cerr<<ch<<endl;; //spt.insert(nowad+j,ch); } str1[x]=‘\0‘; spt.insert2(nowad,str1,x); if (x)ch=getchar(); break; case ‘D‘: scanf("%d\n",&x); spt.erase(nowad,x); break; case‘G‘: scanf("%d\n",&x); spt.print_str(nowad,x); break; case‘P‘: nowad--; break; case‘N‘: nowad++; break; } /* cout<<od<<" "<<x<<endl; if (od[0]==‘I‘)cout<<str1<<endl; cout<<"<<";spt.scan(spt.root);cout<<"["<<nowad<<"]"; cout<<endl;*/ } }catch (const char* err) { cout<<err; return 0; } return 0; }
BZOI 1507 [NOI2003] Editor,布布扣,bubuko.com
原文：http://www.cnblogs.com/mhy12345/p/3805228.html