题目描述
这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义： 
文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。 编写一个程序：? 建立一个空的文本编辑器。? 从输入文件中读入一些操作指令并执行。? 对所有执行过的GET操作，将指定的内容写入输出文件。
输入
输入文件中第一行是指令条数N，以下是需要执行的N个操作。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。
输出
依次对应输入文件中每条GET指令的输出，不得有任何多余的字符。
样例输入
10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get
样例输出
B
t
题解
Splay裸题
本身这道题并不是很难，直接上Splay就能轻易搞定。
然而最恶心的就是输入。
也不知道gets()的机制是什么，在Insert时如果用scanf("%d\n",...)的话，将会无限TLE！（虽然我也不知道为什么）
然后按照网上改成了scanf("%d%*c",...)就A了。。。
这题好像还不需要建树添加，时间也应该不会被卡。
#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;
}
【bzoj1269】[AHOI2006]文本编辑器editor
原文：http://www.cnblogs.com/GXZlegend/p/6498013.html