P4008 文本编辑器NOI2003

admin

题目描述
很久很久以前，DOS3.x的程序员们开始对 EDLIN 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器⋯⋯

多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试） ！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？

为了明确目标，小明对“文本编辑器”做了一个抽象的定义:

文本：由 0 个或多个 ASCII 码在闭区间 [32, 126] 内的字符构成的序列。

光标：在一段文本中用于指示位置的标记，可以位于文本首部，文本尾部或文本的某两个字符之间。

文本编辑器：由一段文本和该文本中的一个光标组成的，支持如下操作的数据结构。如果这段文本为空，我们就说这个文本编辑器是空的。

操作名称        输入文件中的格式        功能
Move(k)           Move k                      将光标移动到第 k 个字符之后，如果 k=0，将光标移到文本开头
Insert(n,s)        Insert n s                  在光标处插入长度为 n 的字符串 s，光标位置不变n≥1
Delete(n)          Delete n                    删除光标后的 n 个字符，光标位置不变，n≥1
Get(n)              Get n                        输出光标后的 n 个字符，光标位置不变，n≥1
Prev()               Prev                         光标前移一个字符
Next()               Next                        光标后移一个字符
你的任务是：

建立一个空的文本编辑器。

从输入文件中读入一些操作并执行。

对所有执行过的 GET 操作，将指定的内容写入输出文件。

输入格式
输入文件 editor.in 的第一行是指令条数 t，以下是需要执行的 t 个操作。其中：

为了使输入文件便于阅读， Insert 操作的字符串中可能会插入一些回车符， 请忽略掉它们（如果难以理解这句话，可以参照样例） 。

除了回车符之外，输入文件的所有字符的 ASCII 码都在闭区间 [32, 126] 内。且行尾没有空格。

这里我们有如下假定：

MOVE 操作不超过 50000个， INSERT 和 DELETE 操作的总个数不超过 4000，PREV 和 NEXT 操作的总个数不超过 200000。

所有 INSERT 插入的字符数之和不超过 2M（1M=1024×1024 字节） ，正确的输出文件长度不超过 3M字节。

DELETE 操作和 GET 操作执行时光标后必然有足够的字符。 MOVE 、 PREV 、 NEXT 操作必然不会试图把光标移动到非法位置。

输入文件没有错误。

对 C++ 选手的提示：经测试，最大的测试数据使用 fstream 进行输入有可能会比使用 stdio 慢约 11 秒。

输出格式
输出文件 editor.out 的每行依次对应输入文件中每条 Get 指令的输出。

输入输出样例
输入
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

输出 #1复制
.\/.
abcde^_^f.\/.ghijklmno

admin

首次见到这个题是NOI2003赛场外，湖南长沙长郡中学，那个时候SPLAY还属于很高深的内容，大家编程用的还是FPC，上午看到这个题我还没有想到SPLAY，那个时候也不会，只感觉需要用一种非线性的数据结构，当时有个想法用二维数组行之间首尾相连，其实也有点像块状数组的感觉，晚上我在长郡中学旁边的一个小旅馆床上郁闷的思考这些题，觉得要拿高分好难呀。十几年过去了，这种题目居然成了板子题。我们用裸的SPLAY来解决。

我在这个楼内记录一下我做这个题的过程，希望对大家有所启发。

admin

显然此题可以用SPLAY来解决，因为我现在已经熟悉SPALY的使用了。所以做题第一步，你的基础知识要丰富，题目做得越多，方法用的越多，感觉就会越好，就会有种条件反射。我既然选择了SPLAY就当做这方面的一个训练吧，当然也可以用块状数组，我以后再发一个块状链表的解题报告。
简单论证下SPLAY的可行性：
序列典型板子，设首尾设一个假节点，我喜欢使用@符号，(因为表达式求值也是这样的，前面序列终结者也是这样条件反射)，那么所有的操作就在2-N+1节点之间进行。
题目有插入，删除，移动光标，输出等几个操作，数据规模最大10^6，若是SPLAY,算比较平衡的树的话深度大约log10^6=20层，保守一点估计不会40层，40下操作可以完成移动，删除，输出等，插入类似线段树建树，也不会超过40下，所以总运算大约在3*10^5*40=8*10^6，应该还能接受。
那么就开始吧，我的特点是步步为营，函数做一个希望对一个，所以先做点测试数据，
第一个：检查初始建树
插入10个字符 1234567890，BSTPr结果应该是@1234567890@
再插入7个ABCDEFG，
光标挪到第3个位子，再插入3个字符XYZ，
光标挪到第13个位子，再插入3个字符###，
这几部要是都对了，插入和移动光标我就基本没有问题，删除和插入没什么两样，输出和删除也几乎一样，move就是求序列中的第几个数，简单。
Pre和Next我倒是有想类似treap等那样找左子树最大或者右子树最小等，但是先不慌，用最笨的方法做对再说。
第二步  测试Get n，
第三步  测试Del
第四步  测试Pre和Next

admin

按照我的SPLAY风格，这次定义A数组为结构体包含 val fa s[2] sz四个域，ArrayPr  BSTPr  R  Splay Pushup只用pushup sz Getkth一切照旧。
这里要在纸上画一画curpos和kth之间的关系，因为一是有假的头尾节点，二是光标在某处还不是具体位置而是一个中间值
我假定的@是我序列的首尾元素，所以题目序列的第k个数在我的程序里是k+1
我定义的光标位置变量为curpos，按题目要求是在第k个字符的后面，0在首位，那么对于我的程序来说，开始curpos=0，对应着我的SPLAY程序就是在第1,2两个元素间插入，那么curpos和我的k的对应关系是  curpos=k+1，就是说，要在curpos处插入的话就是int L=Getkth(rt,k+1)到根，

我是这样一步步写程序的，

admin

第一步，定义A tot root等，建立假节点，读入10个字符建树，然后插入到a数组的12之间。
这里读字符有点技巧，我用的是类似P1420乒乓球里面的读法，考虑到数据很大，使用getchar，其他的都是基本写法，保证准确为第一位，

1. #include <bits/stdc++.h>
   
2. using namespace  std;
   
3. const  int mm=2100000;
   
4. struct Node {
   
5.         char val;
   
6.         int fa,s[2],sz;
   
7. } a[mm];
   
8. int root,tot,curpos,offset;
   
9. void ArrayPr() { /// 调试监视使用
   
10.         cout<<endl<<"  i ";
    
11.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
12.         cout<<endl<<"val ";
    
13.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
14.         cout<<endl<<" s0 ";
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
16.         cout<<endl<<" s1 ";
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
18.         cout<<endl<<" fa ";
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
20.         cout<<endl<<" sz ";
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
22.         cout<<endl;
    
23. }
    
24. int Build(string s,int l,int r) { ///把s串L-R之间的建树
    
25.         if (l>r)return 0;
    
26.         if (l==r) {
    
27.                 a[offset+l].val=s[l],a[offset+l].sz=1;
    
28.                 return l;
    
29.         }
    
30.         if (l<r) {
    
31. 
    
32.                 int m=(l+r)/2;
    
33.                 a[offset+m].val=s[m];
    
34.                 int tl=0,tr=0;
    
35.                 if (m-1>=l) {
    
36.                         tl=Build(s,l,m-1),a[offset+tl].fa=offset+m,a[offset+m].s[0]=offset+tl;
    
37.                 }
    
38.                 if (m+1<=r) {
    
39.                         tr=Build(s,m+1,r),a[offset+tr].fa=offset+m,a[offset+m].s[1]=offset+tr;
    
40.                 }
    
41.                 a[offset+m].sz=r-l+1;
    
42.                 return m;
    
43.         }
    
44. }
    
45. void NewEmpty() { /// 建新的假树
    
46.         a[1].val=a[2].val='@';
    
47.         a[1].s[0]=a[2].s[0]=a[2].s[1]=0,a[1].s[1]=2;
    
48.         a[1].fa=0,a[2].fa=1;
    
49.         a[1].sz=2,a[2].sz=1;
    
50.         root=1,tot=2,curpos=0;
    
51. }
    
52. void BSTPr(int x) {
    
53.         int l=a[x].s[0],r=a[x].s[1];
    
54.         if (l>0) BSTPr(l);
    
55.         cout<<a[x].val;
    
56.         if (r>0) BSTPr(r);
    
57. }
    
58. int main() {
    
59.         int n;
    
60.         cin>>n;
    
61.         NewEmpty();
    
62.         while (n--) {
    
63.                 char opt[10];
    
64.                 scanf("%s", opt);
    
65.                 if (opt[0]=='I') {
    
66.                         int l,i=1;
    
67.                         scanf("%d",&l);
    
68.                         char ch;
    
69.                         string s="#";
    
70.                         while (i<=l) {
    
71.                                 ch=getchar();
    
72.                                 while(ch<32||ch>126) ch=getchar();
    
73.                                 i++;
    
74.                                 s=s+ch;
    
75.                         }
    
76.                         offset=tot;
    
77.                         tot+=l;
    
78.                         int tm=offset+Build(s,1,l);
    
79.                         ArrayPr();
    
80.                         cout<<endl;
    
81.                         BSTPr(tm);
    
82.                 }
    
83.         }
    
84.         return 0;
    
85. }
    
86. /*
    
87. 10
    
88. Insert 10
    
89. abcdefghij
    
90. Insert 10
    
91. 0123456789
    
92. 
    
93. */

复制代码

admin

上面程序我写了10分钟不到，调试了约10-15分钟，在offset那里，因为建树是接在原始A数组后面建立而不是完全的新建，好在我的EXCEL学的还很不错，这个偏移很容易推理和计算，经过后面测试数据检测，暂无问题，
测试答案如下：
10
Insert 10
abcdefghij

  i   1  2  3  4  5  6  7  8  9 10 11 12
val   @  @  a  b  c  d  e  f  g  h  i  j
s0   0  0  0  3  0  0  4  0  0  8  0  0
s1   2  0  0  5  6  0 10  9  0 11 12  0
fa   0  1  4  7  4  5  0 10  8  7 10 11
sz   2  1  1  4  2  1 10  2  1  5  2  1

abcdefghij

再次检查程序，没有发现隐患，现在加上R和SPLAY，试试插入看行不行

admin

加上R和SPLAY，输入输入下代码，现在已经背的很熟，快速录入无错误。

1. 
   
2. void pushup(int x)
   
3. {
   
4.         int l=a[x].s[0],r=a[x].s[1];
   
5.         a[x].sz=a[l].sz+a[r].sz+1;
   
6. }
   
7. int son(int x)
   
8. {
   
9.         int y=a[x].fa;
   
10.         return a[y].s[1]==x;
    
11. }
    
12. void R(int x)
    
13. {
    
14.         int y=a[x].fa;
    
15.         int z=a[y].fa;
    
16.         int k=son(x);
    
17.         int v=a[x].s[k^1];
    
18.         a[y].s[k]=v,a[v].fa=y;
    
19.         a[z].s[son(y)]=x,a[x].fa=z;
    
20.         a[x].s[k^1]=y,a[y].fa=x;
    
21.         pushup(y),pushup(x);
    
22. }
    
23. void Splay(int x,int rt=root)  ///把x旋到rt的位置 默认rt是根
    
24. {
    
25.         rt=a[rt].fa;
    
26.         int y,z;
    
27.         while(a[x].fa!=rt)
    
28.                 {
    
29.                         y=a[x].fa,z=a[y].fa;;
    
30.                         if(z!=rt)
    
31.                                 if(son(x)==son(y))R(y);
    
32.                                 else R(x);
    
33.                         R(x);
    
34.                 }
    
35.         if(rt==0)root=x;
    
36. }
    
37. int Getkth(int rt, int x) ///在RT子树中找第k小
    
38. {
    
39.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
    
40.         if(l+1==x) return rt;
    
41.         if(l+1>x) return Getkth(a[rt].s[0], x); ///左儿子里去找
    
42.         if(l+1<x) return Getkth(a[rt].s[1], x-(l+1));
    
43. }
    

复制代码

在Ins代码段里面加上插入子树的过程

1. int L=Getkth(root,curpos+1);
   
2. int R=Getkth(root,curpos+2);
   
3. Splay(L,root),Splay(R,a[root].s[1]);
   
4. BSTPr(root);

复制代码

验算成功，多次插入结果都是对的强制改动curpos=2 3 5 等也是正确的，这里就基本无问题。
花费了我20多分钟。

admin

下面的删除和删除就很简单，只是int R=Getkth(root,curpos+2)这里在加上一个偏移k就是了。只要保证前面的curpos和k的分析没有问题就行了
MOVE、PREV、NEXT就直接curpos=k；--curpos，++curpos算了。
整理了一个完整程序，

1. #include <bits/stdc++.h>
   
2. using namespace  std;
   
3. const  int mm=2100000;
   
4. struct Node {
   
5.         char val;
   
6.         int fa,s[2],sz;
   
7. } a[mm];
   
8. int root,tot,curpos,offset;
   
9. void ArrayPr() { /// 调试监视使用
   
10.         cout<<endl<<"  i ";
    
11.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
12.         cout<<endl<<"val ";
    
13.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
14.         cout<<endl<<" s0 ";
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
16.         cout<<endl<<" s1 ";
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
18.         cout<<endl<<" fa ";
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
20.         cout<<endl<<" sz ";
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
22.         cout<<endl;
    
23. }
    
24. void pushup(int x) {
    
25.         int l=a[x].s[0],r=a[x].s[1];
    
26.         a[x].sz=a[l].sz+a[r].sz+1;
    
27. }
    
28. int son(int x) {
    
29.         int y=a[x].fa;
    
30.         return a[y].s[1]==x;
    
31. }
    
32. void R(int x) {
    
33.         int y=a[x].fa;
    
34.         int z=a[y].fa;
    
35.         int k=son(x);
    
36.         int v=a[x].s[k^1];
    
37.         a[y].s[k]=v,a[v].fa=y;
    
38.         a[z].s[son(y)]=x,a[x].fa=z;
    
39.         a[x].s[k^1]=y,a[y].fa=x;
    
40.         pushup(y),pushup(x);
    
41. }
    
42. void Splay(int x,int rt=root) { ///把x旋到rt的位置 默认rt是根
    
43.         rt=a[rt].fa;
    
44.         int y,z;
    
45.         while(a[x].fa!=rt) {
    
46.                 y=a[x].fa,z=a[y].fa;;
    
47.                 if(z!=rt)
    
48.                         if(son(x)==son(y))R(y);
    
49.                         else R(x);
    
50.                 R(x);
    
51.         }
    
52.         if(rt==0)root=x;
    
53. }
    
54. int Build(string s,int l,int r) { ///把s串L-R之间的建树
    
55.         if (l>r)return -1;
    
56.         if (l==r) {
    
57.                 a[offset+l].val=s[l],a[offset+l].sz=1;
    
58.                 return l;
    
59.         }
    
60.         if (l<r) {
    
61. 
    
62.                 int m=(l+r)/2;
    
63.                 a[offset+m].val=s[m];
    
64.                 int tl=0,tr=0;
    
65.                 if (m-1>=l) {
    
66.                         tl=Build(s,l,m-1),a[offset+tl].fa=offset+m,a[offset+m].s[0]=offset+tl;
    
67.                 }
    
68.                 if (m+1<=r) {
    
69.                         tr=Build(s,m+1,r),a[offset+tr].fa=offset+m,a[offset+m].s[1]=offset+tr;
    
70.                 }
    
71.                 a[offset+m].sz=r-l+1;
    
72.                 return m;
    
73.         }
    
74. }
    
75. int Getkth(int rt, int x) { ///在RT子树中找第k小
    
76.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
    
77.         if(l+1==x) return rt;
    
78.         if(l+1>x) return Getkth(a[rt].s[0], x); ///左儿子里去找
    
79.         if(l+1<x) return Getkth(a[rt].s[1], x-(l+1));
    
80. }
    
81. 
    
82. void NewEmpty() { /// 建新的假树
    
83.         a[1].val=a[2].val='@';
    
84.         a[1].s[0]=a[2].s[0]=a[2].s[1]=0,a[1].s[1]=2;
    
85.         a[1].fa=0,a[2].fa=1;
    
86.         a[1].sz=2,a[2].sz=1;
    
87.         root=1,tot=2,curpos=0;
    
88. }
    
89. void BSTPr(int x) {
    
90.         int l=a[x].s[0],r=a[x].s[1];
    
91.         if (l>0) BSTPr(l);
    
92.         cout<<a[x].val;
    
93.         if (r>0) BSTPr(r);
    
94. 
    
95. }
    
96. void get(int n) {
    
97.         int t=a[root].s[1];
    
98.         Splay(curpos,root),Splay(curpos+n+1,t);
    
99.         BSTPr(t);
    
100. }
     
101. int main() {
     
102.         int n;
     
103.         cin>>n;
     
104.         NewEmpty();
     
105.         while (n--) {
     
106.                 char opt[10];
     
107.                 scanf("%s", opt);
     
108. 
     
109.                 if (opt[0]=='M') {
     
110.                         int k;
     
111.                         scanf("%d",&k);
     
112.                         curpos=k;
     
113.                         ///Getkth(root,k+1);
     
114.                         ///cout<<"curpos="<<curpos<<endl;
     
115.                 }
     
116. 
     
117.                 if (opt[0]=='I') {
     
118.                         int l,i=1;
     
119.                         scanf("%d",&l);
     
120.                         char ch;
     
121.                         string s="#";
     
122.                         while (i<=l) {
     
123.                                 ch=getchar();
     
124.                                 while(ch<32||ch>126) ch=getchar();
     
125.                                 i++;
     
126.                                 s=s+ch;
     
127.                         }
     
128.                         offset=tot;
     
129.                         tot+=l;
     
130.                         int tm=offset+Build(s,1,l);
     
131. 
     
132.                         Splay(L,root),Splay(R,a[root].s[1]);
     
133.                         a[R].s[0]=tm,a[tm].fa=R;
     
134.                         pushup(R),pushup(L);
     
135.                 }
     
136.                 if (opt[0]=='G') {
     
137.                         int k;
     
138.                         scanf("%d",&k);
     
139.                         int L=Getkth(root,curpos+1);
     
140.                         int R=Getkth(root,curpos+k+2);
     
141.                         Splay(L,root),Splay(R,a[root].s[1]);
     
142.                         BSTPr(a[R].s[0]);
     
143.                         printf("\n");
     
144.                 }
     
145.                 if (opt[0]=='D') {
     
146.                         int k;
     
147.                         scanf("%d",&k);
     
148.                         int L=Getkth(root,curpos+1);
     
149.                         int R=Getkth(root,curpos+k+2);
     
150.                         Splay(L,root),Splay(R,a[root].s[1]);
     
151.                         a[R].s[0]=0;
     
152.                         pushup(R),pushup(L);
     
153.                 }
     
154.                 if (opt[0]=='P') curpos--;
     
155.                 if (opt[0]=='N') curpos++;
     
156.         }
     
157.         return 0;
     
158. }
     
159. /*
     
160. 10
     
161. Insert 10
     
162. abcdefghij
     
163. Move 5
     
164. Insert 10
     
165. 0123456789
     
166. Move 3
     
167. Ins 2
     
168. **
     
169. Move 10
     
170. In 3
     
171. %%%
     
172. Del 3
     
173. 
     
174. 
     
175. */

复制代码

admin

到此 整个程序花了约2-3小时，自己拟了几组数据，好像没有发现问题。
交上去一看，10分！！！！

admin

剩下的我足足花了2小时多来查错，其实程序是没有错的。效率是有问题的。终于在凌晨解决了整个题，从饭后7点到凌晨解决，足足5小时！大部分时间竟然是在调效率！