线段树优化建图——zkw线段树优化建图 B. Legacy Codeforces Round 406 (Div. 1)

B. Legacy Codeforces Round 406 (Div. 1)
板子如下

struct zkwSegtree_improve_graph {
    /* Author : atzk */
    int n , N , rf , r2 , r4 ;
    vector < vector < pair < int , int > > > map ;

    zkwSegtree_improve_graph ( int n ) {
        N = ( 1 << ( __lg ( n + 5 ) + 1 ) ) ;
        rf = N >> 1 , r2 = N << 1 , r4 = N << 2 ;
        map.resize ( r4 ) ;
        build () ;
    }

    void build () {
        for ( int i = 1 ; i < rf ; ++ i ) {
            ll fa = i , ls = i << 1 , rs = i << 1 | 1 ;
            map [ fa ].emplace_back ( ls , 0 ) ;
            map [ fa ].emplace_back ( rs , 0 ) ;
            map [ ls + r2 ].emplace_back ( fa + r2 , 0 ) ;
            map [ rs + r2 ].emplace_back ( fa + r2 , 0 ) ;
        }
        for ( int i = N ; i < r2 ; ++ i ) {
            ll fa = i >> 1 , now = i , son = fa + r2 ;
            map [ fa ].emplace_back ( now , 0 ) ;
            map [ now ].emplace_back ( son , 0 ) ;
        }
    }
    void linkto ( ll now , ll l , ll r , ll w ) {
        now += N ;
        for ( l += N - 1 , r += N + 1 ; l ^ r ^ 1 ; l >>= 1 , r >>= 1 ) {
            if ( ~l & 1 ) map [ now ].emplace_back ( l ^ 1 , w ) ;
            if ( r & 1 ) map [ now ].emplace_back ( r ^ 1 , w ) ;
        }
    }
    void linkfrom ( ll now , ll l , ll r , ll w ) {
        now += N ;
        l += N - 1 , r += N + 1 ;
        if ( ~l & 1 ) map [ l ^ 1 ].emplace_back ( now , w ) ;
        if ( r & 1 ) map [ r ^ 1 ].emplace_back ( now , w ) ;       
        l >>= 1 ; r >>= 1 ;
        for ( ; l ^ r ^ 1 ; l >>= 1 , r >>= 1 ) {
            if ( ~l & 1 ) map [ l ^ 1 + r2 ].emplace_back ( now , w ) ;
            if ( r & 1 ) map [ r ^ 1 + r2 ].emplace_back ( now , w ) ;
        }
    }
    void linkpoint ( ll from , ll to , ll w ) {
        map [ from + N ].emplace_back ( to + N , w ) ;
    }
};

模板题：
洛谷传送门
codeforces传送门
ac code：

# include  <bits/stdc++.h>
using  namespace  std ;

using ll = int64_t ;
using i64 = int64_t ;

namespace predefine {
const long long inf = 0x3f3f3f3f3f3f3f3f ;
using Int = __int128 ;
using pll = pair < ll , ll > ;
# define  IOS  iostream::sync_with_stdio ( 0 ) ; cin.tie ( 0 ) ;

# define af( i , a , b ) for ( ll i = a ; i <= b ; ++ i )
# define df( i , a , b ) for ( ll i = a ; i >= b ; -- i )

# define Dg( x ) cout << " ------- " <<  x << " ------- " << '\n'
# define Dged Dg ( "Debug ed" )
# define Dgop Dg ( "Debug op" )
# define pr( x ) cout << #x << " = " << x << '\n'
# define pn putchar ('\n') 
# define ps cout << "yes" 
# define __fin( a ) freopen ( a , "r" , stdin ) 
# define __fout( a ) freopen ( a , "w+" , stdout ) 

# define lowbit( x ) ( x & ( - x ) ) 
# define endl '\n'
}
using namespace predefine ;
/*

*/

//-----  板子  ---------------------------------------------------------------------------------------------------------
struct zkwSegtree_improve_graph {
    /* Author : atzk */
    int n , N , rf , r2 , r4 ;
    vector < vector < pair < int , int > > > map ;

    zkwSegtree_improve_graph ( int n ) {
        N = ( 1 << ( __lg ( n + 5 ) + 1 ) ) ;
        rf = N >> 1 , r2 = N << 1 , r4 = N << 2 ;
        map.resize ( r4 ) ;
        build () ;
    }

    void build () {
        for ( int i = 1 ; i < rf ; ++ i ) {
            ll fa = i , ls = i << 1 , rs = i << 1 | 1 ;
            map [ fa ].emplace_back ( ls , 0 ) ;
            map [ fa ].emplace_back ( rs , 0 ) ;
            map [ ls + r2 ].emplace_back ( fa + r2 , 0 ) ;
            map [ rs + r2 ].emplace_back ( fa + r2 , 0 ) ;
        }
        for ( int i = N ; i < r2 ; ++ i ) {
            ll fa = i >> 1 , now = i , son = fa + r2 ;
            map [ fa ].emplace_back ( now , 0 ) ;
            map [ now ].emplace_back ( son , 0 ) ;
        }
    }
    void linkto ( ll now , ll l , ll r , ll w ) {
        now += N ;
        for ( l += N - 1 , r += N + 1 ; l ^ r ^ 1 ; l >>= 1 , r >>= 1 ) {
            if ( ~l & 1 ) map [ now ].emplace_back ( l ^ 1 , w ) ;
            if ( r & 1 ) map [ now ].emplace_back ( r ^ 1 , w ) ;
        }
    }
    void linkfrom ( ll now , ll l , ll r , ll w ) {
        now += N ;
        l += N - 1 , r += N + 1 ;
        if ( ~l & 1 ) map [ l ^ 1 ].emplace_back ( now , w ) ;
        if ( r & 1 ) map [ r ^ 1 ].emplace_back ( now , w ) ;       
        l >>= 1 ; r >>= 1 ;
        for ( ; l ^ r ^ 1 ; l >>= 1 , r >>= 1 ) {
            if ( ~l & 1 ) map [ l ^ 1 + r2 ].emplace_back ( now , w ) ;
            if ( r & 1 ) map [ r ^ 1 + r2 ].emplace_back ( now , w ) ;
        }
    }
    void linkpoint ( ll from , ll to , ll w ) {
        map [ from + N ].emplace_back ( to + N , w ) ;
    }
};
//-----  板子  ---------------------------------------------------------------------------------------------------------
/*

*/

ll Pow ( ll a , ll b , ll mod ) { 
	a = a % mod ; ll ans = 1 ; 
	for ( ; b ; b >>= 1 ) { if ( b & 1 ) ans = ( a * ans ) % mod ; a = ( a * a ) % mod ; } 
	return ans ; }

inline ll sum1 ( ll _a ) { return ( _a * ( _a + 1 ) ) >> 1 ; }
inline ll sum2 ( ll _b ) { return _b * ( _b + 1 ) * ( 2 * _b + 1 ) / 6  ; }

ll dx [ 4 ] = { -1 , 0 , 1 , 0 } ;
ll dy [ 4 ] = { 0 , 1 , 0 , -1 } ;

void solve () {
    ll n , q , root ; cin >> n >> q >> root ;

    zkwSegtree_improve_graph g ( n ) ;
    
    while ( q -- ) {
        ll ops ; cin >> ops ; 
        if ( ops == 1 ) {
            ll v , u , w ; cin >> v >> u >> w ;
            g.linkto ( v , u , u , w ) ;
        }
        else if ( ops == 2 ) {
            ll v , l , r , w ; cin >> v >> l >> r >> w ;
            g.linkto ( v , l , r , w ) ;
        }
        else {
            ll v , l , r , w ; cin >> v >> l >> r >> w ;
            g.linkfrom ( v , l , r , w ) ;
        }
    }

    priority_queue < pll , vector < pll > , greater < pll > > qu ;
    qu.emplace ( 0 , root + g.N ) ;

    vector < ll > dp ( g.r4 , inf ) ;

    vector < bool > vis ( g.r4 , 0 ) ;

    while ( !qu.empty () ) {
        auto [ len , now ] = qu.top () ;
        qu.pop () ;
        if ( vis [ now ] ) continue ;
        vis [ now ] = 1 ;
        dp [ now ] = len ;

        for ( auto [ here , len1 ]: g.map [ now ] ) {
            if ( !vis [ here ] ) qu.emplace ( dp [ now ] + len1 , here ) ;
        }
    }
    
    for ( int i = 1 ; i <= n ; ++ i ) {
    	if ( dp [ i + g.N ] == inf ) cout << "-1" << ' ' ;
        else cout << dp [ i + g.N ] << ' ' ;
    }
    return ;
}

int  main () {
	// IOS ;
	// __fin ( "in.in" ) ;
	// init () ;
	ll _ = 1 ;
	// rd ( _ ) ;
  	// cin >> _ ;
	while ( _ -- ) {
		solve () ;
	} 
	return 0 ;
}

/*
//-----  数据  ---------------------------------------------------------------------------------------------------------
8 1 2
3 7 2 2 21
----------
*/