【bzoj1507】[NOI2003]Editor /【bzoj1269】[AHOI2006]文本编辑器editor Splay

【bzoj1507】[NOI2003]Editor

题目描述

输入

输入文件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慢约1秒。

输出

输出文件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

样例输出

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

【bzoj1269】[AHOI2006]文本编辑器editor

题目描述

同上，只是加了一个Rever操作，同时Get操作只输出一个字符

题解

P1507没有翻转，好像可以不用Splay，然而P1269必须使用Splay，故选择一劳永逸，都使用同样的算法（和同样的代码）搞定。

本身这两道题并不是很难，基本上P1269就属于Splay的基础题，P1507连基础题都算不上。。。

然而最恶心的就是输入。

P1507中的多行读入，用gets()会TLE。

必须逐个字符读入！必须逐个字符读入！必须逐个字符读入！

还有，也不知道gets()的机制是什么，在Insert时如果用scanf("%d\n",...)的话，将会无限TLE！（虽然我也不知道为什么）

然后按照网上改成了scanf("%d%*c",...)。

然后这两道题就搞定了。。。

这题好像还不需要建树添加，时间也应该不会被卡。

另：听某神犇说P1507数据可能会在Del时越界，需要取min，反正我是没遇到这种情况，直接交就A了。

bzoj1507:

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 2 * 1024 * 1024 + 100

using namespace std;

int c[2][N] , fa[N] , si[N] , root = 1 , tot = 0;

char ch[N] , opt[10] , str[N];

void pushup(int k)

{

	si[k] = si[c[0][k]] + si[c[1][k]] + 1;

}

void rotate(int &k , int x)

{

	int y = fa[x] , z = fa[y] , l = (c[0][y] != x) , r = l ^ 1;

	if(y == k) k = x;

	else c[c[0][z] != y][z] = x;

	fa[x] = z;

	fa[y] = x;

	fa[c[r][x]] = y;

	c[l][y] = c[r][x];

	c[r][x] = y;

	pushup(y);

	pushup(x);

}

void splay(int &k , int x)

{

	while(x != k)

	{

		int y = fa[x] , z = fa[y];

		if(y != k)

		{

			if(c[0][z] == y ^ c[0][y] == x) rotate(k , x);

			else rotate(k , y);

		}

		rotate(k , x);

	}

}

int find(int k , int x)

{

	if(x <= si[c[0][k]]) return find(c[0][k] , x);

	else if(x > si[c[0][k]] + 1) return find(c[1][k] , x - si[c[0][k]] - 1);

	else return k;

}

void build(int l , int r , int f , int fplace)

{

	if(l > r) return;

	int mid = (l + r) >> 1;

	build(l , mid - 1 , mid , mid + tot);

	build(mid + 1 , r , mid , mid + tot);

	ch[mid + tot] = str[mid];

	fa[mid + tot] = fplace;

	c[mid > f][fplace] = mid + tot;

	pushup(mid + tot);

}

void split(int l , int r)

{

	int a , b;

	a = find(root , l - 1);

	splay(root , a);

	b = find(root , r + 1);

	splay(c[1][root] , b);

}

void del(int k)

{

	if(!k) return;

	del(c[0][k]) , del(c[1][k]);

	c[0][k] = c[1][k] = fa[k] = si[k] = ch[k] = 0;

}

void output(int k)

{

	if(!k) return;

	output(c[0][k]);

	printf("%c" , ch[k]);

	output(c[1][k]);

}

int main()

{

	int n , p = 1 , x , i;

	scanf("%d" , &n);

	build(1 , 2 , 0 , 0);

	tot = 2;

	while(n -- )

	{

		scanf("%s" , opt);

		switch(opt[0])

		{

			case 'M':

			{

				scanf("%d" , &x);

				p = x + 1;

				break;

			}

			case 'I':

			{

				scanf("%d%*c" , &x);

				int l = 0;

				while(str[l + 1] = getchar())

				{

					if(str[l + 1] != '\r' && str[l + 1] != '\n')

					{

						l ++ ;

						if(l == x) break;

					}

				}

				split(p + 1 , p);

				build(1 , x , 0x7fffffff , c[1][root]);

				pushup(c[1][root]);

				pushup(root);

				tot += x;

				break;

			}

			case 'D':

			{

				scanf("%d" , &x);

				split(p + 1 , p + x);

				del(c[0][c[1][root]]);

				c[0][c[1][root]] = 0;

				pushup(c[1][root]);

				pushup(root);

				break;

			}

			case 'G':

			{

				scanf("%d" , &x);

				split(p + 1 , p + x);

				output(c[0][c[1][root]]);

				printf("\n");

				break;

			}

			case 'P': p -- ; break;

			default: p ++ ;

		}

	}

	return 0;

}

bzoj1269:

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 2 * 1024 * 1024 + 100

using namespace std;

int c[2][N] , fa[N] , si[N] , rev[N] , root = 1 , tot = 0;

char ch[N] , opt[10] , str[N];

void pushup(int k)

{

	si[k] = si[c[0][k]] + si[c[1][k]] + 1;

}

void pushdown(int k)

{

	if(rev[k])

	{

		int l = c[0][k] , r = c[1][k];

		swap(c[0][l] , c[1][l]);

		swap(c[0][r] , c[1][r]);

		rev[l] ^= 1 , rev[r] ^= 1;

		rev[k] = 0;

	}

}

void rotate(int &k , int x)

{

	int y = fa[x] , z = fa[y] , l = (c[0][y] != x) , r = l ^ 1;

	if(y == k) k = x;

	else c[c[0][z] != y][z] = x;

	fa[x] = z;

	fa[y] = x;

	fa[c[r][x]] = y;

	c[l][y] = c[r][x];

	c[r][x] = y;

	pushup(y);

	pushup(x);

}

void splay(int &k , int x)

{

	while(x != k)

	{

		int y = fa[x] , z = fa[y];

		if(y != k)

		{

			if(c[0][z] == y ^ c[0][y] == x) rotate(k , x);

			else rotate(k , y);

		}

		rotate(k , x);

	}

}

int find(int k , int x)

{

	pushdown(k);

	if(x <= si[c[0][k]]) return find(c[0][k] , x);

	else if(x > si[c[0][k]] + 1) return find(c[1][k] , x - si[c[0][k]] - 1);

	else return k;

}

void build(int l , int r , int f , int fplace)

{

	if(l > r) return;

	int mid = (l + r) >> 1;

	build(l , mid - 1 , mid , mid + tot);

	build(mid + 1 , r , mid , mid + tot);

	ch[mid + tot] = str[mid];

	fa[mid + tot] = fplace;

	c[mid > f][fplace] = mid + tot;

	pushup(mid + tot);

}

void split(int l , int r)

{

	int a , b;

	a = find(root , l - 1);

	splay(root , a);

	b = find(root , r + 1);

	splay(c[1][root] , b);

}

void del(int k)

{

	if(!k) return;

	del(c[0][k]) , del(c[1][k]);

	c[0][k] = c[1][k] = fa[k] = si[k] = rev[k] = ch[k] = 0;

}

int main()

{

	int n , p = 1 , x , i;

	scanf("%d" , &n);

	build(1 , 2 , 0 , 0);

	tot = 2;

	while(n -- )

	{

		scanf("%s" , opt);

		switch(opt[0])

		{

			case 'M':

			{

				scanf("%d" , &x);

				p = x + 1;

				break;

			}

			case 'I':

			{

				scanf("%d%*c" , &x);

				int l = 0 , sl = 0;

				gets(str + 1);

				split(p + 1 , p);

				build(1 , x , 0x7fffffff , c[1][root]);

				pushup(c[1][root]);

				pushup(root);

				tot += x;

				break;

			}

			case 'D':

			{

				scanf("%d" , &x);

				split(p + 1 , p + x);

				del(c[0][c[1][root]]);

				c[0][c[1][root]] = 0;

				pushup(c[1][root]);

				pushup(root);

				break;

			}

			case 'R':

			{

				scanf("%d" , &x);

				split(p + 1 , p + x);

				int t = c[0][c[1][root]];

				swap(c[0][t] , c[1][t]);

				rev[t] ^= 1;

				break;

			}

			case 'G': printf("%c\n" , ch[find(root , p + 1)]); break;

			case 'P': p -- ; break;

			default: p ++ ;

		}

	}

	return 0;

}

巴特西

【bzoj1507】[NOI2003]Editor /【bzoj1269】[AHOI2006]文本编辑器editor Splay

最新文章

热门文章