首页 > > 程序设计 > C/C++ >

BZOJ1269: [AHOI2006]文本编辑器editor

2018-06-17 21:29:50来源：未知阅读 ()

1269: [AHOI2006]文本编辑器editor

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4671 Solved: 1801
[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操作不会把光标移动到非法位置。? 输入文件没有错误。

Source

鸣谢seter重新制作数据

[Submit][Status][Discuss]

HOME Back

MDZZ块状链表好恶心。。

也没啥好讲的，就是个大暴力

不过网上好像没多少资料

有空整理一下吧

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 const int MAXN=2000000+10;
  8 const int BlockSize=3000 + 100,BlockNum=3000 + 10;
  9 int Cur=0,head,tot;
 10 char str[MAXN];
 11 struct Block
 12 {
 13     int size,nxt;
 14     bool rev;
 15     char a[BlockSize];
 16     void Clear()
 17     {
 18         size=0;nxt=-1,rev=0;
 19     }
 20 }B[BlockNum];
 21 queue<int>q;//鐢ㄤ竴涓槦鍒楁潵缁存姢褰撳墠鏈夊摢浜涘潡
 22 int NewNode()
 23 {
 24     int t=q.front();q.pop();
 25     B[t].Clear();
 26     return t;
 27 }
 28 inline void Pre()
 29 {
 30     while(q.size()!=0)    q.pop();
 31     for(int i=0;i<BlockNum;i++) q.push(i);
 32     head = NewNode();
 33 }
 34 void Find(int &idx,int &cur)
 35 {
 36     while(idx!=-1&&cur>B[idx].size) cur-=B[idx].size,idx=B[idx].nxt;
 37 }
 38 void Pushdown(int idx)
 39 {
 40     if(B[idx].rev) 
 41     {
 42     //    for(int i=0;i<B[idx].size;i++)
 43     //        cout<<B[idx].a[i];cout<<endl;
 44         reverse(B[idx].a,B[idx].a+B[idx].size);
 45     //    for(int i=0;i<B[idx].size;i++)
 46     //        cout<<B[idx].a[i];cout<<endl;
 47         B[idx].rev=0;
 48     }
 49         
 50 }
 51 inline void Split(int idx,int cur)
 52 {
 53     if(idx==-1||cur==B[idx].size)    return ;
 54     Pushdown(idx);
 55     int tot=NewNode();
 56     memcpy(B[tot].a,B[idx].a+cur,sizeof(char) * (B[idx].size-cur) );
 57     B[tot].size=B[idx].size-cur;
 58     B[idx].size=cur;
 59     B[tot].nxt=B[idx].nxt;
 60     B[idx].nxt=tot;
 61 }
 62 void Delet(int idx)
 63 {
 64     q.push(idx);
 65 }
 66 void Merge(int idx)
 67 {
 68     for(int i=idx;i!=-1;i=B[i].nxt)
 69         for(int j=B[i].nxt;j!=-1;j=B[j].nxt)
 70         {
 71             if(B[i].size+B[j].size<=BlockSize)
 72             {
 73                 Pushdown(i);
 74                 Pushdown(j);
 75                 memcpy(B[i].a+B[i].size,B[j].a,sizeof(char) * B[j].size);
 76                 B[i].size+=B[j].size;B[i].nxt=B[j].nxt;
 77                 Delet(j);
 78             }
 79             else break;
 80         }
 81 }
 82 inline void Insert(int cur,int x,char *str)
 83 {
 84     int idx=head;
 85     Find(idx,cur);
 86     Split(idx,cur);
 87     int i=0;//宸茬粡鍔犲叆鐨勪釜鏁?
 88     while(i<x)
 89     {
 90         int Limit=min(BlockSize,x-i);
 91         int tot=NewNode();
 92         memcpy(B[tot].a,str+i,sizeof(char) * Limit);
 93         B[tot].size=Limit;
 94         B[tot].nxt=B[idx].nxt;
 95         B[idx].nxt=tot;
 96         idx=B[idx].nxt;
 97         i+=Limit;
 98     }
 99     Merge(head);
100 }
101 void Print(int cur)
102 {
103     int idx=head;
104     Find(idx,cur);
105     if(cur==B[idx].size) idx=B[idx].nxt,cur=0;
106     Pushdown(idx);
107     printf("%c\n",B[idx].a[cur]);
108 }
109 void Rever(int l,int r)
110 {
111     int idx=head;
112     Find(idx,l);
113     Split(idx,l);
114     int Start=idx,StartNxt=B[idx].nxt;
115     idx=head;
116     Find(idx,r);
117     Split(idx,r);
118     int EndNxt=B[idx].nxt;
119     int Tmp[BlockNum],cnt=0;
120     for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)
121         B[i].rev^=1,Tmp[++cnt]=i;
122     Tmp[++cnt]=Start;Tmp[0]=EndNxt;
123     for(int i=cnt;i>=1;i--)
124         B[Tmp[i]].nxt=Tmp[i-1];
125     Merge(head);
126 }
127 void Dele(int l,int r)
128 {
129     int idx=head;
130     Find(idx,l);
131     Split(idx,l);
132     int Start=idx,StartNxt=B[idx].nxt;
133     idx=head;
134     Find(idx,r);
135     Split(idx,r);
136     int EndNxt=B[idx].nxt;
137     for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)    Delet(i);
138     B[Start].nxt=EndNxt;
139     Merge(head);
140 }
141 int main()  
142 {
143     #ifdef WIN32
144     freopen("a.in","r",stdin);
145     #else
146     #endif
147     int N;scanf("%d",&N);
148     char opt[20];
149     Pre();
150     while(N--)
151     {
152         scanf("%s",opt);
153         if(opt[0]=='M') 
154             scanf("%d",&Cur);
155         else if(opt[0]=='I')
156         {
157             int len;
158             scanf("%d", &len);
159             int i = 0;
160             while(i < len) {char ch = getchar();if(ch >= 32 && ch <= 126) str[i++] = ch;}
161             str[i++] = '\0';
162             Insert(Cur,len,str);
163         }
164         else if(opt[0]=='D')
165         {
166             int x;
167             scanf("%d",&x);
168             Dele(Cur,Cur+x);
169         }
170         else if(opt[0]=='R')
171         {
172             int x;
173             scanf("%d",&x);
174             Rever(Cur,x+Cur);
175         }
176         else if(opt[0]=='G')    
177             Print(Cur);
178         else if(opt[0]=='P')    Cur--;
179         else if(opt[0]=='N')    Cur++;
180     }
181     return 0;
182 }