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

2023-11-07 08:59
文章标签 bzoj splay 文本编辑 editor 1269 ahoi2006

本文主要是介绍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重新制作数据

 

转载于:https://www.cnblogs.com/JSZX11556/p/4593742.html

这篇关于BZOJ 1269: [AHOI2006]文本编辑器editor( splay )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/362577。

相关文章

文本编辑器-Vim

文本编辑器-Vim

http://www.vim.org/ 简单介绍 Vim是一种高度可配置的文本编辑器，用于创建和更改任何类型的文本非常高效。它与大多数UNIX系统和苹果OS X一起被列为 “vi”。 Vim是稳定的，并且不断被开发以变得更好。 其功能包括： 1. 持久的，多级的撤消树 2. 广泛的插件系统 3. 支持数百种编程语言和文件格式 4. 强大的搜索和替换 5. 与许多工具集成 下载
阅读更多...
【BZOJ】1324 Exca王者之剑 最大权独立集

【BZOJ】1324 Exca王者之剑 最大权独立集

传送门：【BZOJ】1324  Exca王者之剑 题目分析：赤裸裸的最大权独立集。。。最小割解决 代码如下： #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , a , b ) for ( int
阅读更多...
【BZOJ】1026: [SCOI2009]windy数 数位DP

【BZOJ】1026: [SCOI2009]windy数 数位DP

传送门：【BZOJ】1026: [SCOI2009]windy数 题目分析：数位DP水题。 代码如下： #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,
阅读更多...
【BZOJ】2152: 聪聪可可 点分治

【BZOJ】2152: 聪聪可可 点分治

传送门：【BZOJ】2152: 聪聪可可 题目分析：记录权值和%3的路径的个数。。。然后去重。。没了。。 代码如下： #include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;typedef lo
阅读更多...
Vue3 使用 富文本编辑器 wangeditor/editor-for-vue 配置详解

Vue3 使用 富文本编辑器 wangeditor/editor-for-vue 配置详解

Vue3 使用 富文本编辑器 wangeditor/editor-for-vue 配置详解 先上官网地址 wangEditor 5 点这里 wangeditor 主要API 配置功能栏 let toolbarConfig = {toolbarKeys: [ "bold", // 字体加粗 "underline", // 字体下划线 "italic", // 字体斜体 "through",
阅读更多...
Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers

Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers

对应POJ 题目：点击打开链接 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 72765 Accepted: 22465Case Time Limit: 2000MS Description You have N integers, A1
阅读更多...
Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain

Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain

对应HDU题目：点击打开链接 Play with Chain Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4571    Accepted Submission(s): 1859 Problem Descript
阅读更多...
一款可以替代Notepad++的免费高级文本编辑器

一款可以替代Notepad++的免费高级文本编辑器

Kate 文本编辑器是一款跨平台的免费高级文本编辑器，具有丰富的功能和特性。它支持标签页、代码高亮、多文件查找、垂直/水平视图、侧边栏、颜色主题等特性，类似于Notepad++。它以其多功能性和易用性广受好评。Kate 支持多文档界面（MDI）和标签页，允许用户同时编辑和查看多个文件，无论是单独在一个窗口中还是在分割视图中。 相较于其他文本编辑器，Kate 提供了更为全面的功能和更好的跨平台支持
阅读更多...
最新版本typora下载安装（保姆级教程）、文本编辑器typora解除破解（包括新旧版本）

最新版本typora下载安装（保姆级教程）、文本编辑器typora解除破解（包括新旧版本）

首先针对旧版本，原本只需要替换 app.asar 文件即可。具体的操作步骤可以见这篇文章：旧版本解除步骤 问题：评论反应，说方法不行，仍激活破除不了，而且还导致软件使用不了，于是这里介绍新的方法（针对新版本） 新旧版本区分：值得是破解的新旧方法，而不是绝对意义上的新旧版本 建议使用新版本：比如这里以 1.7.x 为例（其余高版本激活方法一样） 一、下载 1、Typora 官网下
阅读更多...
java文本编辑软件代码

java文本编辑软件代码

这是小编在csdn第一篇博文，闲话不多说，直接上代码：   该编辑器能够类似记事本，能实现文件的打开，保存，文本的复制，粘贴，查找，替换等功能，效果图如下：   源码如下： package A;import java.awt.BorderLayout;import java.awt.CheckboxMenuItem;import java.awt.Container;impor
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2