bzoj 1269 bzoj 1507 Splay处理文本信息
2024-08-28 11:34:16
bzoj 1269
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1269
大致思路：
用splay维护整个文本信息，splay树的中序遍历即为该文本。
收获：
1、可以先在文本开始和结尾个插入一个节点，然后每次操作都适当调整位置，这样可以减少特判（插入一段文本到0位置，在最后插入一段文本。。。）
2、查找一段文本[lf,rg]，可以先找到位置为lf-1的节点（因为1，不用特判没有了），splay到根，再找到rg+1的节点，旋转到根的下面，这样根右子节点的左子树就是我们要找的内容。
3、翻转一段文本，有点像线段树，给节点打上lazy标记，因为删除、插入、翻转等操作都是建立在查找制定位置的节点这一操作上的，所以我们只需要在查找操作中下传标记。（下传标记和标记都要用“反转”方式而不是“设置”方式，因为以前有可能已经有了标志）
#include <cstdio>
#include <cstring>
#include <iostream>
#define maxn 2100000
using namespace std; struct Splay {
int pre[maxn], son[maxn][], siz[maxn], ntot, root;
char val[maxn];
bool inv[maxn];
int trash[maxn], stot; int newnode( char ch, int p ) {
int nd;
if( stot ) nd = trash[stot--];
else nd = ++ntot;
val[nd] = ch;
pre[nd] = p;
son[nd][] = son[nd][] = ;
siz[nd] = ;
inv[nd] = false;
return nd;
}
Splay():ntot(),stot(){
root = newnode( '^', );
son[root][] = newnode( '$', root );
}
void pushdown( int nd ) {
if( inv[nd] ) {
swap( son[nd][], son[nd][] );
if( son[nd][] ) inv[son[nd][]] ^= true;
if( son[nd][] ) inv[son[nd][]] ^= true;
inv[nd] = false;
}
}
void update( int nd ) {
siz[nd] = siz[son[nd][]]+siz[son[nd][]]+;
}
void rotate( int nd, int d ) {
int p = pre[nd];
int s = son[nd][!d];
int ss = son[s][d]; son[nd][!d] = ss;
son[s][d] = nd;
if( p ) son[p][ nd==son[p][] ] = s;
else root = s; pre[nd] = s;
pre[s] = p;
if( ss ) pre[ss] = nd; update( nd );
update( s );
}
void splay( int nd, int top ) {
while( pre[nd]!=top ) {
int p = pre[nd];
int nl = nd==son[p][];
if( pre[p]==top ) {
rotate( p, nl );
} else {
int pp = pre[p];
int pl = p==son[pp][];
if( pl==nl ) {
rotate( pp, pl );
rotate( p, nl );
} else {
rotate( p, nl );
rotate( pp, pl );
}
}
}
}
int find( int pos ) {
int nd = root;
while() {
pushdown( nd );
int ls = siz[son[nd][]];
if( pos<=ls ) {
nd = son[nd][];
} else if( pos>=ls+ ) {
nd = son[nd][];
pos -= ls+;
} else {
break;
}
}
return nd;
}
int build( int lf, int rg, int p, char *str ) { // [lf,rg]
if( lf>rg ) return ;
if( lf==rg ) return newnode( str[lf], p );
int mid = (lf+rg)>>;
int nd = newnode( str[mid], p );
son[nd][] = build( lf, mid-, nd, str );
son[nd][] = build( mid+, rg, nd, str );
update( nd );
return nd;
}
void insert( int pos, int n, char *str ) {
int lnode = find( pos );
int rnode = find( pos+ );
splay( lnode, );
splay( rnode, lnode );
int nd = build( , n-, rnode, str );
son[rnode][] = nd;
splay( nd, );
}
void erase_subtree( int nd ) {
if( !nd ) return;
erase_subtree( son[nd][] );
erase_subtree( son[nd][] );
trash[++stot] = nd;
}
void erase( int lf, int rg ) {
int lnode = find(lf-);
int rnode = find(rg+);
splay( lnode, );
splay( rnode, lnode );
int nd = son[rnode][];
son[rnode][] = ;
erase_subtree( nd );
update( rnode );
splay( rnode, );
}
void reverse( int lf, int rg ) {
int lnode = find( lf- );
int rnode = find( rg+ );
splay( lnode, );
splay( rnode, lnode );
inv[son[rnode][]] ^= true;
}
char get( int pos ) {
int nd = find(pos);
char ch = val[nd];
splay( nd, );
return ch;
}
void print( int nd ) {
if( !nd ) return;
print(son[nd][]);
fprintf( stderr, "%c", val[nd] );
print(son[nd][]);
}
}; Splay T;
int n, cur_pos;
int len;
char str[maxn]; void getstr( int len ) {
while( (str[]=getchar())!='\n' );
for( int i=; i<len; i++ )
str[i] = getchar();
}
int main() {
scanf( "%d", &n );
cur_pos = ;
for( int i=; i<=n; i++ ) {
char ch[];
int k;
scanf( "%s", ch );
//fprintf( stderr, "Process %d: %s\n", i, ch );
switch( ch[] ) {
case 'M':
scanf( "%d", &k );
cur_pos = k+;
break;
case 'I':
scanf( "%d", &len );
getstr(len);
T.insert( cur_pos, len, str );
break;
case 'D':
scanf( "%d", &len );
T.erase( cur_pos+, cur_pos+len );
break;
case 'R':
scanf( "%d", &len );
T.reverse( cur_pos+, cur_pos+len );
break;
case 'G':
printf( "%c\n", T.get(cur_pos+) );
break;
case 'P':
cur_pos--;
break;
case 'N':
cur_pos++;
break;
}
//fprintf( stderr, "Finished, curent state: " );
//T.print(T.root);
//fprintf( stderr, "\n" );
//fprintf( stderr, "cur_pos=%d\n\n", cur_pos );
} }
bzoj 1507
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1507
和上一道题差不多（还简单一点，不用反转），但输出要求是一段，splay可以每次调用读取一个字符（因为有splay操作，所以挨在一起的点每次就在根的右边）
#include <cstdio>
#define maxn 2100000 struct Splay {
int pre[maxn], son[maxn][], siz[maxn], ntot, root;
int trash[maxn], stot;
char val[maxn]; int newnode( char ch, int p ) {
int nd;
if( stot ) nd = trash[stot--];
else nd = ++ntot;
val[nd] = ch;
pre[nd] = p;
son[nd][] = son[nd][] = ;
siz[nd] = ;
return nd;
}
Splay() {
root = newnode( '^', );
son[root][] = newnode( '$', root );
update( root );
}
void update( int nd ) {
siz[nd] = siz[son[nd][]]+siz[son[nd][]]+;
}
void rotate( int nd, int d ) {
int p = pre[nd];
int s = son[nd][!d];
int ss = son[s][d]; son[nd][!d] = ss;
son[s][d] = nd;
if( p ) son[p][ nd==son[p][] ] = s;
else root = s; pre[nd] = s;
pre[s] = p;
if( ss ) pre[ss] = nd; update( nd );
update( s );
}
void splay( int nd, int top ) {
while( pre[nd]!=top ) {
int p = pre[nd];
int nl = nd==son[p][];
if( pre[p]==top ) {
rotate( p, nl );
} else {
int pp = pre[p];
int pl = p==son[pp][];
if( nl==pl ) {
rotate( pp, pl );
rotate( p, nl );
} else {
rotate( p, nl );
rotate( pp, pl );
}
}
}
}
int find( int pos ) {
int nd = root;
while( ) {
int ls = siz[son[nd][]];
if( pos<=ls ) {
nd = son[nd][];
} else if( pos>=ls+ ) {
nd = son[nd][];
pos -= ls+;
} else {
break;
}
}
return nd;
}
int build( int p, int lf, int rg, char *str ) {
if( lf>rg ) return ;
int mid = (lf+rg)>>;
int nd = newnode( str[mid], p );
son[nd][] = build( nd, lf, mid-, str );
son[nd][] = build( nd, mid+, rg, str );
update( nd );
return nd;
}
void insert( int pos, int n, char *str ) {
int lnd = find(pos);
int rnd = find(pos+);
splay(lnd,);
splay(rnd,lnd);
son[rnd][] = build( rnd, , n-, str );
splay( son[rnd][], );
}
void erase_subtree( int nd ) {
if( !nd ) return;
erase_subtree( son[nd][] );
erase_subtree( son[nd][] );
trash[++stot] = nd;
}
void erase( int lf, int rg ) {
int lnd = find(lf-);
int rnd = find(rg+);
splay( lnd, );
splay( rnd, lnd );
erase_subtree( son[rnd][] );
son[rnd][] = ;
update( rnd );
splay( rnd, );
}
char get( int pos ) {
int nd = find(pos);
char ch = val[nd];;
splay( nd, );
return ch;
}
}; int n, cur_pos, len;
Splay T; char *getstr( int len ) {
static char str[maxn];
while( getchar()!='\n' );
for( int i=; i<len; i++ )
while( (str[i] = getchar())=='\n' );
return str;
} int main() {
scanf( "%d", &n );
cur_pos = ;
for( int i=; i<=n; i++ ) {
char ch[];
int k;
scanf( "%s", ch );
// fprintf( stderr, "Process %d: %s\n", i, ch );
switch(ch[]) {
case 'M':
scanf( "%d", &k );
cur_pos = k+;
break;
case 'I':
scanf( "%d", &len );
T.insert( cur_pos, len, getstr(len) );
break;
case 'D':
scanf( "%d", &len );
T.erase( cur_pos+, cur_pos+len );
break;
case 'G':
scanf( "%d", &len );
for( int i=; i<=len; i++ )
putchar( T.get(cur_pos+i) );
printf( "\n" );
break;
case 'P':
cur_pos--;
break;
case 'N':
cur_pos++;
break;
}
}
}
最新文章
- APP接口自动化测试JAVA+TestNG(二)之TestNG简介与基础实例
- JDK自带工具列表
- sublime 3 安装go环境
- SAX解析DOM4J的方法总结
- mesos 学习笔记1 -- mesos安装和配置
- iOS-微信-分享
- WAF绕过的技巧
- Python使用SMTP发送邮件[HTML格式、送带附件]
- Qt 自定义model实现文件系统的文件名排序（重定义sort函数即可。忽然开窍了：其实捕捉点击Header事件，内部重排序，全部刷新显示即可）
- 解决Eclipse导出javadoc乱码问题
- ADB操作多台设备
- Oracle中not exists 与not in 的使用情况
- C++ 中的权限控制
- 【Node.js】Event Loop执行顺序详解
- Python成长之路_装饰器
- 浅谈C10K问题
- Dubbo与Zookeeper、SpringMVC整合和使用
- 基于Rabbit实现的RPC
- 函数计算 Python 连接 SQL Server 小结
- 取消a标签或者onclick在移动端点击时的背景颜色