记录编号	23245	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]文本编辑器	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C	运行时间	1.243 s
提交时间	2011-03-04 20:03:49	内存使用	0.29 MiB

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

#define ISLSON(X) ((X)==(X)->p->left)
#define ISRSON(X) ((X)==(X)->p->right)

typedef struct ST_SP_NODE {
	int size;
	char ch;
	struct ST_SP_NODE *p, *left, *right;
} SP_node;

typedef struct ST_SPTREE {
	struct ST_SP_NODE *NIL, *root;
} SP_tree;

FILE *fin, *fout;

void SP_init (SP_tree *tree)
{
	tree->NIL = malloc(sizeof(SP_tree));
	tree->root = tree->NIL->p = tree->NIL;
	tree->NIL->size = 0;
}

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;
}

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;
}

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_node *SP_prevnode (const SP_node *node)
{
	SP_node *pi = node->left;
	while (pi->size && pi->right->size)
		pi = pi->right;

	return pi;
}

SP_node *SP_succnode (const SP_node *node)
{
	SP_node *pi = node->right;
	while (pi->size && pi->left->size)
		pi = pi->left;

	return pi;
}

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;
}

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);
}

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_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));
}

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;
}

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':
			{
				fscanf(fin, "%d", &arg);
				curr = SP_find(text.root, arg + 1);
				SP_splay(&text, curr, text.NIL);
				break;
			}

			case 'I':
			{
				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':
			{
				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':
			{
				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':
			{
				curr = SP_prevnode(curr);
				SP_splay(&text, curr, text.NIL);
				break;
			}

			case 'N':
			{
				curr = SP_succnode(curr);
				SP_splay(&text, curr, text.NIL);
				break;
			}
		}
	}

	fclose(fin);
	fclose(fout);

	return 0;
}