[NOI2003] [Splay(伸展树)] EDITOR2003 文本编辑器

文本编辑器

时间限制	2000 ms
内存限制	128 MB

【问题描述】

很久很久以前，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	光标后移一个字符

比如从一个空的文本编辑器开始，依次执行操作INSERT(13, “Balanced□tree”)，MOVE(2)，DELETE(5)，NEXT()，INSERT(7, “□editor”)，MOVE(0)，GET(15)后，会输出“Bad□editor□tree”，如下表所示：

操作	操作前的文本	操作后的结果
INSERT(13, “Balanced□tree”)	\| （只有光标，文本为空）	\|Balanced□tree
MOVE(2)	\|Balanced□tree	Ba\|lanced□tree
DELETE(5)	Ba\|lanced□tree	Ba\|d□tree
NEXT()	Ba\|d□tree	Bad\|□tree
INSERT(7, “□editor”)，	Bad\|□tree	Bad\|□editor□tree
MOVE(0)	Bad\|□editor□tree	\|Bad□editor□tree
GET(15)	\|Bad□editor□tree	输出“Bad□editor□tree”

上表中，“|”表示光标，“□”表示空格。你的任务是：

建立一个空的文本编辑器。
从输入文件中读入一些操作指令并执行。
对所有执行过的GET操作，将指定的内容写入输出文件。

【输入文件】

输入文件的第一行是指令条数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慢约1秒，因此建议在可以的情况下使用后者。

【输出文件】

输出文件的每行依次对应输入文件中每条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

【样例输出】

.\/.
abcde^_^f.\/.ghijklmno

题解

田神牛推荐用Splay（伸展树，一种排序二叉树）做这道题，于是看了看论文，学习了Splay。

关于Splay的基本知识，推荐阅读： The Magical Splay

针对本题说一些问题：

本题用的“二叉排序树”，不需要key域，即排序的关键字，只需要数据域存储字符。如果硬要说key的话，就算是字符的顺序吧。插入时只要插到光标所在节点与其后继节点之间即可，排序二叉树操作不会破坏顺序。
Insert插入字符串操作，尽管可以一个一个字符插入，但把字符串转换为一颗子树插入会更有效率。把字符串转换为树并没有什么要求，我为了省事直接转换成一个链了。
对于这道题，Splay在Delete操作上比其他平衡树要有优势。把光标所在节点伸展到跟，再把删除部分的下一个节点伸展到根的右子树，则要删除的所有节点就在根的右子树的左子树，直接截断即可（没free内存，这不是正确的编程态度 - -）。
在文本起始处和末尾处各插入一个占位字符，会使编程方便些。
Get操作时，仿照删除操作，把光标所在节点伸展到跟，再把要获取部分的下一个节点伸展到根的右子树，则要获取的所有节点就在根的右子树的左子树，然后对该子树进行中序遍历输出字符。

以下是我的代码，由于Splay是单独写的，程序代码保留了大量封装残余 ^_^

最近写的代码都很长，不知道是好是坏……

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct ST_SP_NODE {
	int size; //子结点数
	char ch; //数据域
	struct ST_SP_NODE *p, *left, *right;
} SP_node; //伸展树结点, 对于本题, 不需要key域.

typedef struct ST_SPTREE {
	struct ST_SP_NODE *NIL, *root; //NIL:哨兵 root:根结点
} SP_tree; //伸展树

FILE *fin, *fout; //全局变量, 输入输出文件

/*
 * < ISLSON 判断X是否为父节点的左孩子 >
 * < ISRSON 判断X是否为父节点的右孩子 >
 */
#define ISLSON(X) ((X)==(X)->p->left)
#define ISRSON(X) ((X)==(X)->p->right)

/* < SP_init 初始化树 > */
void SP_init (SP_tree *tree)
{
	tree->NIL = malloc(sizeof(SP_tree));
	tree->root = tree->NIL->p = tree->NIL;
	tree->NIL->size = 0;
}

/* < SP_R_rotate 右旋 > */
void SP_R_rotate (SP_tree *tree, SP_node *node)
{
	SP_node *l = node->left;

	l->p = node->p;
	if (node == tree->root)
		tree->root = l;
	else if (ISLSON(node))
		node->p->left = l;
	else
		node->p->right = l;

	node->p = l;
	node->left = l->right;
	l->right->p = node;
	l->right = node;

	l->size = node->size;
	node->size = node->left->size + node->right->size + 1;
}

/* < SP_L_rotate 左旋 > */
void SP_L_rotate (SP_tree *tree, SP_node *node)
{
	SP_node *r = node->right;

	r->p = node->p;
	if (node == tree->root)
		tree->root = r;
	else if (ISLSON(node))
		node->p->left = r;
	else
		node->p->right = r;

	node->p = r;
	node->right = r->left;
	r->left->p = node;
	r->left = node;

	r->size = node->size;
	node->size = node->left->size + node->right->size + 1;
}

/*
 * < SP_splay 树的伸展 >
 * 把结点node伸展为其祖先结点dest的子节点.
 * 如果dest==NIL, 伸展到根.
 */
void SP_splay (SP_tree *tree, SP_node *node, SP_node *dest)
{
	while (node->p != dest)
	{
		if (node->p->p == dest)
		{
			if (ISLSON(node))
				SP_R_rotate(tree, node->p);
			else
				SP_L_rotate(tree, node->p);
		}
		else if (ISLSON(node))
		{
			if (ISLSON(node->p))
			{
				SP_R_rotate(tree, node->p->p);
				SP_R_rotate(tree, node->p);
			}
			else
			{
				SP_R_rotate(tree, node->p);
				SP_L_rotate(tree, node->p);
			}
		}
		else
		{
			if (ISRSON(node->p))
			{
				SP_L_rotate(tree, node->p->p);
				SP_L_rotate(tree, node->p);
			}
			else
			{
				SP_L_rotate(tree, node->p);
				SP_R_rotate(tree, node->p);
			}
		}
	}
}

/* < SP_prevnode 求前驱结点 > */
SP_node *SP_prevnode (const SP_node *node)
{
	SP_node *pi = node->left;
	while (pi->size && pi->right->size)
		pi = pi->right;

	return pi;
}

/* < SP_succnode 求后继结点 > */
SP_node *SP_succnode (const SP_node *node)
{
	SP_node *pi = node->right;
	while (pi->size && pi->left->size)
		pi = pi->left;

	return pi;
}

/*
 * < SP_inserttree 插入子树 >
 * 将结点树为l的以node为根的子树插入到curr结点后继处.
 * 如果curr==NULL, 直接把tree的根设为该子树.
 */
void SP_inserttree (SP_tree *tree, SP_node *curr,
					SP_node *node, const int l)
{
	if (!curr)
	{
		tree->root = node;
		tree->root->p = tree->NIL;
		return;
	}

	SP_splay(tree, curr, tree->NIL);
	SP_node *pi = tree->root->right, *pj = tree->root;

	tree->root->size += l;
	while (pi->size)
	{
		pj = pi;
		pi->size += l;
		pi = pi->left;
	}

	node->p = pj;
	if (pj != tree->root)
		pj->left = node;
	else
		pj->right = node;
}

/*
 * < SP_freetree 释放子树内存 >
 * 释放子树node和其所有子结点的内存, 用于删除子树后的内存释放.
 * 对于本题, 为了提高速度, 并没有递归释放所有废弃内存.
 */
void SP_freetree (SP_tree *tree, SP_node *node)
{
	if (node == tree->root)
		tree->root = tree->NIL;
	else
	{
		if (ISLSON(node))
			node->p->left = tree->NIL;
		else
			node->p->right = tree->NIL;

		SP_node *pi;
		for (pi=node->p; pi!=tree->NIL; pi=pi->p)
			pi->size = pi->left->size + pi->right->size +1;
	}

	free(node);
}

/*
 * < SP_deleteall 删除连续多个结点 >
 * 删除序号在l和r的序号之间的所有结点.
 */
void SP_deleteall (SP_tree *tree, SP_node *l, SP_node *r)
{
	SP_splay(tree, l, tree->NIL);
	SP_node *pre = SP_prevnode(l);

	SP_splay(tree, r, tree->NIL);
	SP_node *suc = SP_succnode(r);

	if (pre != tree->NIL)
		SP_splay(tree, pre, tree->NIL);
	if (suc != tree->NIL)
		SP_splay(tree, suc, pre);

	if (suc != tree->NIL)
		SP_freetree(tree, suc->left);
	else if (pre != tree->NIL)
		SP_freetree(tree, pre->right);
	else
		SP_freetree(tree, tree->root);
}

/* < SP_find 查找第k个结点 > */
SP_node *SP_find (SP_node *node, const int k)
{
	if (node->left->size + 1 == k)
		return node;
	else if (node->left->size >= k)
		return SP_find(node->left, k);
	else
		return SP_find(node->right, k-(node->left->size+1));
}

/*
 * < str2spnode 字符串转换成树 >
 * 将长度为len的字符串按顺序转换为一个树, 并返回根.
 * 用于题中的Insert插入字符串操作.
 */
SP_node *str2spnode (const char *str, const int len, SP_node *NIL)
{
	SP_node *root = malloc(sizeof(SP_node)), *pi;
	int i;

	root->p = root->left = root->right = NIL;
	root->size = len;
	root->ch = str[0];

	pi = root;
	for (i=1; i<len; i++)
	{
		pi->right = malloc(sizeof(SP_node));
		pi->right->p = pi;
		pi = pi->right;

		pi->left = pi->right = NIL;
		pi->size = len-i;
		pi->ch = str[i];
	}

	return root;
}

/*
 * < TRV_inorder 中序遍历树 >
 * 输出以node为根的子树的中序遍历.
 * 用于题中的Get获取字符串操作.
 */
void TRV_inorder (const SP_node *node)
{
	if (node->left->size)
		TRV_inorder(node->left);

	fputc(node->ch, fout);

	if (node->right->size)
		TRV_inorder(node->right);
}

int main ()
{
	fin = fopen("editor2003.in", "r"),
	fout = fopen("editor2003.out", "w");

	int T, i;
	SP_tree text;
	SP_node *curr;

	fscanf(fin, "%d", &T);

	SP_init(&text);
	SP_inserttree (&text, NULL, str2spnode("{", 1, text.NIL), 1);
	curr = text.root;
	SP_inserttree (&text, text.root, str2spnode("}", 1, text.NIL), 1);

	for (i=0; i<T; i++)
	{
		char cmd[50];
		int arg;
		fscanf(fin, "%s", cmd);

		switch (cmd[0])
		{
			while (fgetc(fin) != '\n') continue;

			case 'M': // Move 移动光标
			{
				fscanf(fin, "%d", &arg);
				curr = SP_find(text.root, arg + 1);
				SP_splay(&text, curr, text.NIL);
				break;
			}

			case 'I': // Insert 插入字符串
			{
				fscanf(fin, "%d", &arg);
				char *arg2 = malloc((arg+1)*sizeof(char)), *pi, c;

				pi = arg2;
				while (pi!=arg2+arg)
					if ((c = fgetc(fin)) >= 32)
						*(pi++) = c;

				SP_inserttree (&text, curr,
						str2spnode(arg2, arg, text.NIL), arg);
				break;
			}

			case 'D': // Delete 删除字符串
			{
				fscanf(fin, "%d", &arg);
				SP_node *pend = SP_find(curr, curr->left->size + arg + 1);
				SP_deleteall(&text, SP_succnode(curr), pend);
				break;
			}

			case 'G': // Get 获取字符串
			{
				fscanf(fin, "%d", &arg);
				SP_node *pend = SP_find(text.root, curr->left->size + arg + 2);
				SP_splay(&text, curr, text.NIL);
				SP_splay(&text, pend, text.root);
				TRV_inorder(text.root->right->left);
				fputc('\n', fout);
				break;
			}

			case 'P': // Prev 光标前移
			{
				curr = SP_prevnode(curr);
				SP_splay(&text, curr, text.NIL);
				break;
			}

			case 'N': // Next 光标后移
			{
				curr = SP_succnode(curr);
				SP_splay(&text, curr, text.NIL);
				break;
			}
		}
	}

	fclose(fin);
	fclose(fout);

	return 0;
}

下面是我写的原版Splay（含有key域的普通排序二叉树）的插入节点代码，供参考：

void SP_insert (SP_tree *tree, const int key)
{
	SP_node *pi = tree->root, *pj = tree->NIL;

	while (pi != tree->NIL)
	{
		pi->size++;
		pj = pi;
		if (key > pi->key)
			pi = pi->right;
		else
			pi = pi->left;
	}

	SP_node *newnode = malloc(sizeof(SP_node));
	newnode->p = pj;
	newnode->left = newnode->right = tree->NIL;
	newnode->key = key;
	newnode->size = 1;

	if (pj == tree->NIL)
		tree->root = newnode;
	else if (key > pj->key)
		pj->right = newnode;
	else
		pj->left = newnode;

	SP_splay(tree, newnode, tree->NIL);
}