BZOJ 1269: [AHOI2006]文本编辑器editor( splay )

splay..( BZOJ 1507 题目基本相同..双倍经验 )

-----------------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

 

#define rep( i , n ) for( int i = 0 ; i < n ; ++i )

#define clr( x , c ) memset( x , c , sizeof( x ) )

 

using namespace std;

 

const int maxn = 2000000;

const int maxnode = maxn + 500;

 

char seq[ maxn ];

int cur = 0;

 

struct Node *pt , *null;

 

struct Node {

Node *ch[ 2 ] , *p;

int s;

char c;

bool rev;

Node( char _c = 'N' ) : c( _c ) {

ch[ 0 ] = ch[ 1 ] = p = null;

s = 1;

rev = false;

}

inline void relax() {

if( rev ) {

rev = false;

rep( i , 2 ) if( ch[ i ] != null )

   ch[ i ] -> Rev();

}

}

inline bool d() {

return p -> ch[ 1 ] == this;

}

inline void setc( Node* c , int d ) {

ch[ d ] = c;

c -> p = this;

}

inline void Rev() {

rev ^= 1;

swap( ch[ 0 ] , ch[ 1 ] );

}

inline void upd() {

s = ch[ 0 ] -> s + ch[ 1 ] -> s + 1;

}

void* operator new( size_t ) {

return pt++;

}

};

 

Node *root;

Node mem[ maxnode ];

 

//[ l , r )

Node* build( int l , int r ) {

if( l >= r ) return null;

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

Node* t = new Node( seq[ m ] );

t -> setc( build( l , m ) , 0 );

t -> setc( build( m + 1 , r ) , 1 );

t -> upd();

return t;

}

 

void rot( Node* t ) {

Node* p = t -> p;

p -> relax();

t -> relax();

int d = t -> d();

p -> p -> setc( t , p -> d() );

p -> setc( t -> ch[ d ^ 1 ] , d );

t -> setc( p , d ^ 1 );

p -> upd();

if( p == root ) root = t;

}

 

void splay( Node* t , Node* f = null ) {

for( Node* p = t -> p ; p != f ; p = t -> p ) {

if( p -> p != f ) 

   p -> d() != t -> d() ? rot( t ) : rot( p );

rot( t );

}

t -> upd();

}

 

Node* select( int k ) {

for( Node* t = root ; ; ) {

t -> relax();

int s = t -> ch[ 0 ] -> s;

if( k == s ) return t;

if( k > s ) 

   k -= s + 1 , t = t -> ch[ 1 ];

else 

   t = t -> ch[ 0 ];

}

}

 

Node* &get( int l , int r ) {

l-- , r++;

Node *L = select( l ) , *R = select( r );

splay( L );

splay( R , L );

return R -> ch[ 0 ];

}

 

void init() {

pt = mem;

null = new( Node );

null -> s = 0;

root = build( 1 , 3 );

}

 

#define ok( c ) ( c >= 32 && c <= 126 )

void Read( int len ) {

int p = 0;

char c = getchar();

while( ! ok( c ) ) c = getchar();

while( ok( c ) ) {

seq[ p++ ] = c;

if( p == len ) break;

c = getchar();

}

}

 

int main() {

// freopen( "test.in" , "r" , stdin );

seq[ 1 ] = seq[ 2 ] = ' ';

init();

int m , len;

cin >> m;

char s[ 15 ];

while( m-- ) {

scanf( " %s" , s );

if( s[ 0 ] == 'M' ) scanf( "%d" , &cur );

else if( s[ 0 ] == 'I' ) {

scanf( "%d" , &len );

Read( len );

Node* L = select( cur ) , *R = select( cur + 1 );

splay( L );

splay( R , L );

R -> setc( build( 0 , len ) , 0 );

R -> upd();

L -> upd();

} else if( s[ 0 ] == 'D' ) {

scanf( "%d" , &len );

Node* &t = get( cur + 1 , cur + len );

Node* p = t -> p;

t = null;

p -> upd();

p -> p -> upd();

} else if( s[ 0 ] == 'R' ) {

scanf( "%d" , &len );

Node* &t = get( cur + 1 , cur + len );

t -> Rev();

} else if( s[ 0 ] == 'G' ) {

Node* t = select( cur + 1 );

printf( "%c\n" , t -> c );

} else 

   s[ 0 ] == 'P' ? cur-- : cur++;

}

return 0;

}

-----------------------------------------------------------------------------

1269: [AHOI2006]文本编辑器editor

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2404  Solved: 888
[Submit][Status][Discuss]

Description

这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义：   文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。 编写一个程序： 建立一个空的文本编辑器。 从输入文件中读入一些操作指令并执行。 对所有执行过的GET操作，将指定的内容写入输出文件。

Input

输入文件中第一行是指令条数N，以下是需要执行的N个操作。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。

Output

依次对应输入文件中每条GET指令的输出，不得有任何多余的字符。

Sample Input

10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get

Sample Output

B
t

HINT

对输入数据我们有如下假定： MOVE操作不超过50 000个，INSERT、DELETE和ROTATE操作作的总个数不超过6 000，GET操作不超过20 000个，PREV和NEXT操作的总个数不超过20 000。 所有INSERT插入的字符数之和不超过2M（1M=1 024*1 024）。 DELETE操作、ROTATE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。 输入文件没有错误。

Source

鸣谢seter重新制作数据