题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3192
直接splay和优先队列暴力维护即可，记得n1=0,n2=0的特判。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std ;
#define MAXN 100010
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define F( t ) father[ t ]
#define G( t )F(F( t ))
#define S( t ) size[ t ]
#define T( t ) tag[ t ]
#define clear( t )memset( t ,0,sizeof( t ))
#define C( t )( t ==L(F( t )))
#define update( t )S( t )=S(L( t ))+S(R( t ))+1
#define ll long long
struct Object{
int v , t ;
bool operator<(const Object &a )const{
return v < a.v ;
}
Object(int _v ,int _t ):v ( _v ),t ( _t ){
}
};
priority_queue < Object > Q ;
int left[ MAXN ], right[ MAXN ], father[ MAXN ], size[ MAXN ];
bool tag[ MAXN ];
void Init( ){
clear( left ),clear( right ),clear( father ),clear( size ),clear( tag );
}
void pushdown(int t ){
if(T( t )&& t ){
swap(L( t ),R( t ));
T(L( t ))^=true,T(R( t ))^=true,T( t )^=true;
}
}
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 ){
pushdown( t );
while(L( t ))pushdown( t =L( t ));
return t ;
}
int n1 , n2 , top1 , top2 ;
ll ans =0;
int main( ){
Init( );
scanf("%d%d",&n1 ,&n2 );
for(int i =0; i ++< n1 ;){
int x ;scanf("%d",&x );
Q.push(Object( x , i ));
S( i )=1;
}
for(int i =0; i ++< n2 ;){
int x ;scanf("%d",&x );
Q.push(Object( x , n1 + i ));
S( i + n1 )=1;
}
for(int i =1; i ++< n1 ;){
splay( i -1);
F(R( i -1)= i )= i -1;update( i -1);
}
if( n1 )F(R( n1 )= n1 + n2 +1)= n1 ;
if( n2 )F(R( n1 + n2 )= n1 + n2 +2)= n1 + n2 ;
S( n1 + n2 +1)=S( n1 + n2 +2)=1;
top1 =1, top2 = n1 +1;
if(! n1 ) top1 = n1 + n2 +1;
if(! n2 ) top2 = n1 + n2 +2;
for(int i =1; i ++< n2 ;){
splay( n1 + i -1);
F(R( n1 + i -1)= n1 + i )= n1 + i -1;update( n1 + i -1);
}
for(int i =0; i ++< n1 + n2 ;){
Object v = Q.top( ); Q.pop( );
splay( v.t );pushdown( v.t ); ans +=S(L( v.t ));
if(Min( v.t )== top1 ){
splay( top2 );
T(L( v.t ))^=true;
F(L( top2 )=L( v.t ))= top2 ;update( top2 );
top2 =Min( top2 );splay( top2 );
F( top1 =R( v.t ))=0; top1 =Min( top1 );
splay( top1 );
}else{
splay( top1 );
T(L( v.t ))^=true;
F(L( top1 )=L( v.t ))= top1 ;update( top1 );
top1 =Min( top1 );splay( top1 );
F( top2 =R( v.t ))=0; top2 =Min( top2 );
splay( top2 );
}
}
printf("%lld\n", ans );
return 0 ;
}
网友评论