题目：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;
}
网友评论