NOI 2003 文本编辑器

NOI Add comments378 views

网上这个题大多数的题解都是基于块状链表的,我的方法是用伸展树Splay。Splay这个东西真是太强大了,灵活得令我五体投地。还是NB的Splay操作,就是把任意一个节点提到根位置。

首先建立一棵伸展树,要记录size以便快速定位。为了方便,在树中插入一个虚拟的头节点,以后每次Move到第k个字符之后只需变成把第k+1个元素Splay到根位置。以后根结点就是光标位置了(光标前面的一个元素)。

插入一段字符串,要先把这段字符串建成一个Splay,怎么建都行,我是把它猥琐地建成了一条链。如果当前光标位置是最后一位,直接把新建 的树接到根节点右子树。否则把根结点的后继节点Splay到根节点右子树的根位置,接下来把新建的树接到根节点右子树根节点的左子树下面。这种插入的方法 常数较小,时间复杂度为O(L*logN)。要注意维护size。

删除也很容易,如果根结点的位置为k,要删除的长度为len,把第k+len+1这个元素Splay到根结点的右子树根位置,然后把它的左子树删掉就行了。特殊的,如果第k+len+1个元素不存在,只需把根节点的右子树全部删除。

输出一段字符串可以效仿删除,只不过不用删掉,而是把它输出出来。极不建议用递归实现中序遍历的输出,因为Splay可能很不平衡,这样有 可能爆掉系统堆栈,所以要手动模拟栈实现。但是这种方法有些复杂了,其实可以一个一个得查找出来输出,经尝试这样不会增加很多的运行时间,却使程序缩短了 不少。

我写了3.5K代码,230行程序,还不算太长,不过运行起来要比块状链表快多了,所有数据都在0.8s内跑过了,10个测试点总运行时间为3.5s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
/* 
 * Problem: NOI2003 editor
 * Author: Guo Jiabao
 * Time: 2009.5.17 16:56
 * State: Solved
 * Memo: Splay 线性建树插入 线性输出
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXS=1024*1024*2;
struct SplayTree
{
	struct SplayNode
	{
		SplayNode *left,*right,*father;
		int size,value;
		int lsize() {return left?left->size:0;}
		int rsize() {return right?right->size:0;}
	};
	SplayNode *root,SS[MAXS],*Stack[MAXS];
	int SC,Spos[MAXS];
	SplayNode* newSplayNode(int value,SplayNode *f)
	{
		SS[SC].left = SS[SC].right = 0;
		SS[SC].father = f;
		SS[SC].size = 1;
		SS[SC].value = value;
		SC++;
		return SS+SC-1;
	}
	void init()
	{
		SC=0;
		root=newSplayNode('#',0);
	}
	void Update(SplayNode *x)
	{
		x->size=x->lsize() + x->rsize() + 1;
	}
	void Zig(SplayNode *x)
	{
		SplayNode *y=x->father;
		y->left=x->right;
		if (x->right)
			x->right->father=y;
		x->father=y->father;
		if (y->father)
		{
			if (y->father->left==y)
				y->father->left=x;
			else
				y->father->right=x;
		}
		y->father=x;
		x->right=y;
		Update(y);
		Update(x);
	}
	void Zag(SplayNode *x)
	{
		SplayNode *y=x->father;
		y->right=x->left;
		if (x->left)
			x->left->father=y;
		x->father=y->father;
		if (y->father)
		{
			if (y->father->left==y)
				y->father->left=x;
			else
				y->father->right=x;
		}
		y->father=x;
		x->left=y;
		Update(y);
		Update(x);
	}
	void Splay(SplayNode *x,SplayNode *f)
	{
		while (x->father != f)
		{
			if (x->father->father == f)
			{
				if (x == x->father->left)
					Zig(x);
				else
					Zag(x);
			}
			else if (x->father->father->left == x->father)
			{
				if (x == x->father->left)
					Zig(x->father),Zig(x);
				else
					Zag(x),Zig(x);
			}
			else
			{
				if (x == x->father->right)
					Zag(x->father),Zag(x);
				else
					Zig(x),Zag(x);
			}
		}
		if (f==0)
			root=x;
	}
	void Select(int k,SplayNode *f)
	{
		SplayNode *x=root;
		for (int l;k!= (l=x->lsize()) + 1 ;)
		{
			if (k <= l)
				x=x->left;
			else
			{
				k-=l+1;
				x=x->right;
			}
		}
		Splay(x,f);
	}
	void Insert(int *Str,int len)
	{
		SplayNode *x=newSplayNode(Str[1],0),*r,*y;
		r=x;
		for (int i=2;i<=len;i++)
		{
			x->right = newSplayNode(Str[i],x);
			x=x->right;
		}
		if (root->right)
		{
			Select(root->lsize()+2,root);
			y=root->right;
			y->left = r;
		}
		else
		{
			y=root;
			y->right=r;
		}
		r->father = y;
		for (;x;x=x->father)
			Update(x);
	}
	void Delete(int len)
	{
		if (root->lsize() + 2 + len <= root->size)
		{
			Select(root->lsize() + 2 + len,root);
			root->right->left=0;
			Update(root->right);
		}
		else
			root->right=0;
		Update(root);
	}
	void Get(int len)
	{
		SplayNode *x=root;
		int k=x->lsize()+1;
		for (int i=1;i<=len;i++)
		{
			Select(k+i,root);
			putchar(root->right->value);
		}
		putchar('\n');
	}
}Splay;
int N,Str[MAXS],Position;
void init()
{
	freopen("editor2003.in","r",stdin);
	freopen("editor2003.out","w",stdout);
	scanf("%d",&N);
	Splay.init();
}
void solve()
{
	int i,c,t,l;
	char Cmd[10];
	for (i=1;i<=N;i++)
	{
		while ((c=getchar())==10 || c==13);ungetc(c,stdin);
		for (t=0;(c=getchar())!=' ' && c!=10 && c!=13;)
			Cmd[++t]=c;
		switch (Cmd[1])
		{
			case 'M':
				scanf("%d",&t);
				Splay.Select(t+1,0);
				Position=t+1;
				break;
			case 'P':
				Splay.Select(--Position,0);
				break;
			case 'N':
				Splay.Select(++Position,0);
				break;
			case 'I':
				scanf("%d",&l);
				for (t=0;t<l;)
				{
					while ((c=getchar())==10 || c==13);
					Str[++t]=c;
				}
				Splay.Insert(Str,l);
				break;
			case 'D':
				scanf("%d",&l);
				Splay.Delete(l);
				break;
			case 'G':
				scanf("%d",&l);
				Splay.Get(l);
				break;
		}
	}
}
int main()
{
	init();
	solve();
	return 0;
}

Maybe you like

标签:, , , ,


10 Responses to “NOI 2003 文本编辑器”

  1. Feng Yi Says:
    Internet Explorer 6.0Windows XP

    程序很棒

    [回复]

    BYVoid 回复:
    Firefox 3.5.5Windows 7

    謝謝誇獎

    [回复]

  2. YQD Says:
    Internet Explorer 6.0Windows XP

    SPLAY 很神奇 不过C的看不太懂
    我用块链0.4S内A的

    [回复]

  3. Edward_mj Says:
    Internet Explorer 6.0;Windows XP

    弱问:
    SPLAY可能很不平衡的话。
    那相对于直接排序二叉树BST有什么优势呢?

    [回复]

    BYVoid 回复:
    Firefox 3.5.7Windows 7

    Splay就是靠它的不平衡實現的低時間複雜度,Splay不是平衡樹,證明參見任何一本數據結構書。

    Splay不用任何附加域。

    [回复]

  4. Edward_mj Says:
    Internet Explorer 6.0;Windows XP

    哈哈,我写了个SBT居然比你的程序快。
    在我这台老爷机上,我跑了5.00s,你的跑了6.22s

    [回复]

    BYVoid 回复:
    Firefox 3.5.7Windows 7

    這道題用SBT,你是如何維護插入鍵值和順序的?

    [回复]

    Edward_mj 回复:
    Internet Explorer 6.0;Windows XP

    这个就把字符的前后位置当SBT得关键字呗。

    [回复]

  5. zhengfy1 Says:
    Internet Explorer 6.0Windows 2000

    大牛从哪里搞到的03年数据?能不能也发给我一份?

    [回复]

  6. inowfordream Says:
    Google Chrome 3.0.195.0Windows 7

    能够给一份测试数据我么?感谢万分!

    [回复]

Leave a Reply

37 queries. 0.668 seconds. Designed by NattyWP .
Images by desEXign.