NOI 2003 文本编辑器

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