BZOJ-3648: 寝室管理（点分治+平衡树）
2019-03-17 本文已影响2人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3648
首先这题求树或一个环套树上面的长度>=k的路径数，那么如果是树直接点分治掉没问题，考虑环套树的情况，如果路径在同一棵树上面，对所有树点分治即可，如果在环上，那么我们沿着顺时针方向扫两圈，平衡树维护一下，然后加加路径上新出现的点，再减掉消掉的点，然后平衡树整体加减一个数这个东西可以弄个时间戳记录一下，然后弄个delta维护即可，这样就平均每个点进平衡树1次，删掉1次，所以复杂度是O(n log^2 n + n log n)前面那个是点分的复杂度。
代码（长的233啊，还好码了一个多小时后就一A了，要不实在调不动）：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std ;
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
const int maxn = 101000 ;
const int maxm = 201000 ;
const int maxv = 401000 ;
struct edge {
edge *next ;
int t , v ;
} E[ maxm ] ;
edge *ept = E , *head[ maxn ] ;
inline void Init_edge( ) {
memset( head , 0 , sizeof( head ) ) ;
}
inline void add( int s , int t , int v ) {
ept -> t = t , ept -> v = v , ept -> next = head[ s ] ; head[ s ] = ept ++ ;
}
inline void addedge( int s , int t , int v ) {
add( s , t , v ) , add( t , s , v ) ;
}
int delta[ maxv ] , idx = 0 ;
struct node {
int ky , mn , pr , sz ;
node *lc , *rc ;
inline void update( ) {
sz = lc -> sz + rc -> sz + 1 ;
}
} bst[ maxv ] ;
node *pt , *null , *root ;
inline void Init_bst( ) {
pt = bst ; null = pt ++ ;
null -> lc = null -> rc = null , null -> pr = null -> sz = 0 ;
root = null ;
}
inline void right( node* &t ) {
node *k = t -> lc ;
t -> lc = k -> rc ; t -> update( ) ;
k -> rc = t ; k -> update( ) ;
t = k ;
}
inline void left( node* &t ) {
node *k = t -> rc ;
t -> rc = k -> lc ; t -> update( ) ;
k -> lc = t ; k -> update( ) ;
t = k ;
}
void Insert( int key , node* &t ) {
if ( t == null ) {
t = pt ++ ;
t -> lc = t -> rc = null , t -> sz = 1 , t -> ky = key , t -> mn = idx , t -> pr = rand( ) ;
return ;
}
t -> sz ++ ;
if ( key <= t -> ky + delta[ idx ] - delta[ t -> mn ] ) {
Insert( key , t -> lc ) ; if ( t -> lc -> pr > t -> pr ) right( t ) ;
} else {
Insert( key , t -> rc ) ; if ( t -> rc -> pr > t -> pr ) left( t ) ;
}
}
inline int Rank( int key , node *t ) {
int rec = 0 ;
for ( ; t != null ; ) {
if ( key <= t -> ky + delta[ idx ] - delta[ t -> mn ] ) {
rec += t -> rc -> sz + 1 ; t = t -> lc ;
} else t = t -> rc ;
}
return rec ;
}
void Delete( int key , node* &t ) {
int k = t -> ky + delta[ idx ] - delta[ t -> mn ] ;
if ( key == k ) {
if ( t -> lc == null ) {
t = t -> rc ; return ;
} else if ( t -> rc == null ) {
t = t -> lc ; return ;
} else if ( t -> lc -> pr > t -> rc -> pr ) {
right( t ) ; Delete( key , t -> rc ) ;
} else {
left( t ) ; Delete( key , t -> lc ) ;
}
} else if ( key < k ) Delete( key , t -> lc ) ; else Delete( key , t -> rc ) ;
t -> update( ) ;
}
bool used[ maxn ] , flag[ maxn ] ;
int n , m , k ;
typedef long long ll ;
ll ans = 0 ;
int sz[ maxn ] , dep[ maxn ] , rt , rv ;
#define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )
void gets( int now , int fa ) {
sz[ now ] = 1 ;
travel( now ) if ( p -> t != fa && ! flag[ p -> t ] && ! used[ p -> t ] ) {
gets( p -> t , now ) ; sz[ now ] += sz[ p -> t ] ;
}
}
void getr( int now , int fa ) {
bool Flag = ( sz[ rv ] - sz[ now ] ) <= ( sz[ rv ] >> 1 ) ;
if ( Flag ) travel( now ) if ( p -> t != fa && ! flag[ p -> t ] && ! used[ p -> t ] ) {
if ( sz[ p -> t ] > ( sz[ rv ] >> 1 ) ) {
Flag = false ; break ;
}
}
if ( Flag ) rt = now ; else travel( now ) if ( p -> t != fa && ! flag[ p -> t ] && ! used[ p -> t ] ) {
getr( p -> t , now ) ;
if ( rt ) break ;
}
}
int ch[ maxn ] , cn ;
void getc( int now , int fa ) {
ch[ ++ cn ] = now , dep[ now ] = dep[ fa ] + 1 ;
travel( now ) if ( p -> t != fa && ! used[ p -> t ] && ! flag[ p -> t ] ) getc( p -> t , now ) ;
}
void solve( int now ) {
gets( now , 0 ) ;
rt = 0 , rv = now ; getr( now , 0 ) ;
dep[ rt ] = 0 ; Init_bst( ) ; idx = 0 ; Insert( 1 , root ) ;
travel( rt ) if ( ! flag[ p -> t ] && ! used[ p -> t ] ) {
cn = 0 ; getc( p -> t , rt ) ;
rep( i , cn ) ans += ll( Rank( k - dep[ ch[ i ] ] , root ) ) ;
rep( i , cn ) Insert( dep[ ch[ i ] ] + 1 , root ) ;
}
used[ rt ] = true ;
travel( rt ) if ( ! flag[ p -> t ] && ! used[ p -> t ] ) solve( p -> t ) ;
}
int cv[ maxn ] , vn = 0 , sta[ maxn ] , tp = 0 , pos[ maxn ] ;
void dfs( int now , int v ) {
sta[ pos[ now ] = ++ tp ] = now ;
travel( now ) if ( p -> v != v ) {
if ( ! pos[ p -> t ] ) dfs( p -> t , p -> v ) ; else {
REP( i , pos[ p -> t ] , tp ) {
flag[ cv[ vn ++ ] = sta[ i ] ] = true ;
}
}
if ( vn ) break ;
}
-- tp ;
}
int mes[ maxn ][ 2 ] ;
int main( ) {
srand( 12 ) ;
Init_edge( ) ;
scanf( "%d%d%d" , &n , &m , &k ) ;
rep( i , m ) {
int s , t ; scanf( "%d%d" , &s , &t ) ; addedge( s , t , i ) ;
}
memset( flag , 0 , sizeof( flag ) ) , memset( used , false , sizeof( used ) ) ;
if ( m == n - 1 ) {
solve( 1 ) ;
} else {
memset( pos , 0 , sizeof( pos ) ) ; dfs( 1 , 0 ) ;
Rep( i , vn ) {
flag[ cv[ i ] ] = false ; solve( cv[ i ] ) ; flag[ cv[ i ] ] = true ;
}
Init_bst( ) ; delta[ idx = 0 ] = 0 ;
memset( used , false , sizeof( used ) ) ;
rep( i , ( vn - 1 ) ) {
delta[ idx + 1 ] = delta[ idx ] + 1 ; ++ idx ;
dep[ cv[ i ] ] = 1 , ch[ cn = 1 ] = cv[ i ] ;
travel( cv[ i ] ) if ( ! flag[ p -> t ] ) getc( p -> t , cv[ i ] ) ;
rep( j , cn ) {
Insert( dep[ ch[ j ] ] , root ) ;
mes[ ch[ j ] ][ 0 ] = dep[ ch[ j ] ] , mes[ ch[ j ] ][ 1 ] = idx ;
}
}
Rep( i , vn ) {
dep[ cv[ i ] ] = 1 , ch[ cn = 1 ] = cv[ i ] ;
travel( cv[ i ] ) if ( ! flag[ p -> t ] ) getc( p -> t , cv[ i ] ) ;
rep( j , cn ) ans += ll( Rank( k - dep[ ch[ j ] ] , root ) ) ;
if ( i == vn - 1 ) break ;
delta[ idx + 1 ] = delta[ idx ] + 1 ; ++ idx ;
rep( j , cn ) Insert( dep[ ch[ j ] ] , root ) ;
cn = 0 ; getc( cv[ i + 1 ] , 0 ) ;
rep( j , cn ) Delete( mes[ ch[ j ] ][ 0 ] + delta[ idx ] - delta[ mes[ ch[ j ] ][ 1 ] ] , root ) ;
}
}
printf( "%lld\n" , ans ) ;
return 0 ;
}
