题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2733
实在是被动态规划虐的体无完肤了（CF上一道状压调了好久都没写出来QaQ）,只能过来继续水数据结构了。
思路很明显，既然是k最值，那就平衡树或者是权值线段树维护一下，然后要维护连通性，就用并查集维护，至于树的合并问题，每次把小的那棵树暴力合并到大的里面就好啦（启发式合并，这个操作是均摊O(n log n)的，算上插入O( log n )的复杂度就是O( n log^2 n )，为什么？想想并查集的按rank合并就可以啦~）
代码（SBT+并查集+启发式合并）：
d058ccbf6c81800a11d51d69b33533fa828b47a0.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAXN 100010
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define K( t ) key[ t ]
#define S( t ) size[ t ]
#define update( t ) S( t )=S(L( t ))+S(R( t ))+1
int left[ MAXN ], right[ MAXN ], key[ MAXN ], size[ MAXN ], n , m , q ;
void left_ratote(int&t ){
int k =R( t );
R( t )=L( k );update( t );
L( k )= t ;update( k );
t = k ;
}
void right_ratote(int&t ){
int k =L( t );
L( t )=R( k );update( t );
R( k )= t ;update( k );
t = k ;
}
void maintain(int&t ){
if(S(L(L( t )))>S(R( t ))){
right_ratote( t );
maintain(R( t ));maintain( t );
return;
}
if(S(R(R( t )))>S(L( t ))){
left_ratote( t );
maintain(L( t ));maintain( t );
return;
}
if(S(R(L( t )))>S(R( t ))){
left_ratote(L( t ));right_ratote( t );
maintain(L( t )),maintain(R( t ));maintain( t );
return;
}
if(S(L(R( t )))>S(L( t ))){
right_ratote(R( t ));left_ratote( t );
maintain(L( t )),maintain(R( t ));maintain( t );
return;
}
}
void Insert(int u ,int&t ){
if(! t ){
t = u ;
L( t )=R( t )=0,S( t )=1;
return;
}
Insert( u ,K( u )<K( t )?L( t ):R( t ));
update( t );maintain( t );
}
int Rank(int k ,int t ){
if(S( t )<= k ||! t )return -1;
if( k ==S(L( t )))return t ;
return k <S(L( t ))?Rank( k ,L( t )):Rank( k -S(L( t ))-1,R( t ));
}
int father[ MAXN ], roof[ MAXN ];
int find_roof(int t ){
int i = t , j = t ;
for(; father[ i ]; i = father[ i ]);
while( father[ j ]){
int k = father[ j ];
father[ j ]= i ;
j = k ;
}
return i ;
}
int dfn[ MAXN ], cnt ;
void dfs(int t ){
dfn[++ cnt ]= t ;
if(L( t ))dfs(L( t ));
if(R( t ))dfs(R( t ));
}
void Union(int u ,int t ){
int k =find_roof( u ), v =find_roof( t );
if( k == v )return;
if(S( roof[ k ])>S( roof[ v ]))swap( k , v );
cnt =0;dfs( roof[ k ]);
for(int i =0; i ++< cnt ;)Insert( dfn[ i ], roof[ v ]);
father[ k ]= v ;
}
int main( ){
L(0)=R(0)=S(0)=0;
scanf("%d%d",&n ,&m );
for(int i =0; i ++< n ;){
scanf("%d",&K( i ));
L( i )=R( i )=0,S( i )=1, roof[ i ]= i ;
}
while( m --){
int s , t ;scanf("%d%d",&s ,&t );
Union( s , t );
}
scanf("%d",&q );
while( q --){
int ch ;for( ch =getchar( );!( ch >='A'&& ch <='Z'); ch =getchar( ));
if( ch =='B'){
int s , t ;scanf("%d%d",&s ,&t );
Union( s , t );
}else{
int x , k ;scanf("%d%d",&x ,&k );
printf("%d\n",Rank( k -1, roof[find_roof( x )]));
}
}
return 0;
}
网友评论