美文网首页信息学竞赛题解(IO题解)
BZOJ-2333: [SCOI2011]棘手的操作(splay

BZOJ-2333: [SCOI2011]棘手的操作(splay

作者: AmadeusChan | 来源:发表于2018-10-16 20:37 被阅读1次

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2333

刚开始看到是动态图问题吓晕了,后来发现没有删边操作,那么就好办多了:由于只需要合并,不需要拆开,所以直接splay暴力维护即可,对于全体最值,本来想打个堆维护的,不过犯了懒,就直接multiset水过去了~

代码(很慢很慢。。。Splay+STL 常数异常巨大):

0823dd54564e9258a08582929e82d158ccbf4e1c.jpg.png
#include <cstdio>

#include <algorithm>

#include <cstring>

#include <set>

 

using namespace std ;

 

#define MAXN 300010

#define L( t ) left[ t ]

#define R( t ) right[ t ]

#define F( t ) father[ t ]

#define G( t )F(F( t ))

#define M( t ) Max[ t ]

#define V( t ) value[ t ]

#define S( t ) sign[ t ]

#define C( t )( t ==L(F( t )))

#define clear( t )memset( t ,0,sizeof( t ))

#define inf 0x7fffffff

 

multiset <int> S ;

 

int left[ MAXN ], right[ MAXN ], father[ MAXN ], Max[ MAXN ], value[ MAXN ], sign[ MAXN ];

int n , m ;

 

void pushdown(int t ){

    if( t &&S( t )){

        V( t )+=S( t ),M( t )+=S( t );

        S(L( t ))+=S( t ),S(R( t ))+=S( t );

        S( t )=0;

    }

}

 

void update(int t ){

    pushdown( t );pushdown(L( t )),pushdown(R( t ));

    M( t )=max(V( t ),max(M(L( t )),M(R( t ))));

}

 

void zag(int t ){

    pushdown( t );pushdown(R( t ));

    int k =R( t ), u =F( t );bool flag =C( t );

    F(R( t )=L( k ))= t ;update( t );

    F(L( k )= t )= k ;update( k );

    F( k )= u ;if( u )if( flag )L( u )= k ;else R( u )= k ;

}

 

void zig(int t ){

    pushdown( t );pushdown(L( t ));

    int k =L( t ), u =F( t );bool flag =C( t );

    F(L( t )=R( k ))= t ;update( t );

    F(R( k )= t )= k ;update( k );

    F( k )= u ;if( u )if( flag )L( u )= k ;else R( u )= k ;

}

 

void splay(int t ){

    while(F( t )){

        pushdown(G( t )),pushdown(F( t )),pushdown( t );

        if(!G( t ))if(C( t ))zig(F( t ));else zag(F( t ));else{

            if(C( t )){

                if(C(F( t )))zig(G( t ));zig(F( t ));

            }else{

                if(!C(F( t )))zag(G( t ));zag(F( t ));

            }

        }

    }

}

 

int MIN(int t ){

    for(;L( t ); t =L( t ));return t ;

}

 

int MAX(int t ){

    for(;R( t ); t =R( t ));return t ;

}

 

int roof(int t ){

    splay( t );return MIN( t );

}

 

int delta =0;

 

int main(  ){

    clear( left ),clear( right ),clear( father ),clear( Max ),clear( value ),clear( sign );

    Max[0]= value[0]=- inf ;

    scanf("%d",&n );

    for(int i =0; i ++< n ;){

        scanf("%d",&value[ i ]);

        Max[ i ]= value[ i ], S.insert( value[ i ]);

    }

    scanf("%d",&m );

    while( m --){

        char s[10];scanf("%s", s );

        int x , y , u , v ;

        if( s[0]=='U'){

            scanf("%d%d",&x ,&y );

            if(roof( x )!=roof( y )){

                splay( x ),splay( y );

                pushdown( x ),pushdown( y );

                if(M( x )<M( y )){

                    S.erase( S.find(M( x )));

                    splay( u =MIN( y ));pushdown( u );

                    F(L( u )= x )= u ;

                }else{

                    S.erase( S.find(M( y )));

                    splay( u =MAX( x ));pushdown( u );

                    F(R( u )= y )= u ;

                }

            }

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

            if( s[1]=='1'){

                scanf("%d%d",&x ,&v );

                splay( x );pushdown( x );

                int u =M( x );

                V( x )+= v ;update( x );

                if(M( x )!= u ){

                    S.erase( S.find( u ));

                    S.insert(M( x ));

                }

            }else if( s[1]=='2'){

                scanf("%d%d",&x ,&v );

                splay( x );pushdown( x );

                S.erase( S.find(M( x )));

                S( x )= v ;pushdown( x );

                S.insert(M( x ));

            }else if( s[1]=='3'){

                scanf("%d",&v ); delta += v ;

            }

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

            if( s[1]=='1'){

                scanf("%d"  ,&x );

                splay( x );pushdown( x );

                printf("%d\n",V( x )+ delta );

            }else if( s[1]=='2'){

                scanf("%d",&x );

                splay( x );pushdown( x );

                printf("%d\n",M( x )+ delta );

            }else if( s[1]=='3'){

                printf("%d\n",*(-- S.end(  ))+ delta );

            }

        }

    }

    return 0;

}

相关文章

  • BZOJ-2333: [SCOI2011]棘手的操作(splay

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2333 刚...

  • Splay

    题目链接:普通平衡树 splay: 题目链接:文艺平衡树 区间翻转: 题目链接:Permutation Trans...

  • Splay

    适用题目特征 维护区间翻转。 原理 想要翻转区间,只要将Splay重构如下。 并且在每次操作后,都模仿类似线段树l...

  • link-cut-tree

    dfs: splay: access: lca:

  • Splay Tree

  • 数据结构与算法分析 —— C 语言描述:伸展树

    伸展树(splay tree)保证从空树开始任意连续 M 次对树的操作最多花费 时间。虽然这种保证并不排除任意一次...

  • 平衡树

    Binary Index Tree AVL Splay Treap Scapegoat Tree Treap(wi...

  • About 5-25

    To do list 09:00 ~ 10:00 splay复习 √10:00 ~ 10:30英语测验 √10...

  • splay学习笔记(上)

    前不久其实已经学过splay了,但是总觉得似乎不能灵活地改造它,于是重新学习了一波。 感谢https://oi.m...

  • BZOJ_1503 郁闷的出纳员

    1.题目相关 标签:Splay 题目地址:http://www.lydsy.com/JudgeOnline/pro...

网友评论

    本文标题:BZOJ-2333: [SCOI2011]棘手的操作(splay

    本文链接:https://www.haomeiwen.com/subject/gelkzftx.html