HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )
Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth
題意:
給一棵節點帶權的樹。每次詢問一條路徑,問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。
制約:
1 ≤ N, Q ≤ 1e5
1 ≤ A[ i ] ≤ 1e9
解法:
第一種方法是用莫隊,將時間戳記做好,進去和出來的時候都塞進一個 vector,這麼一來,路徑可以用這個 vector 上的區間來描述。若一個元素在那區間裡出現兩次就無視它的影響,因為代表它不在路徑裡。這個做法 93 分。
第二種是用持久化 Trie。讓每一個節點都帶有一個持久化 Trie。具體來說,對於 u 的兒節點 v,root[ v ] = add( root[ u ], A[ v ] )。這麼一來,假如要求的是 u, v 路徑上的答案,那麼找到 p = lca( u, v ),( 為了方便假設 p != u and p != v ) 則 u, v 路徑上形成的 Trie 是 root[ u ] + root[ v ] - 2 * root[ p ] + A[ p ]。
時間 / 空間複雜度:
O( N lg A + Q lg A )
// Mo's TLE, score: 93 #include <bits/stdc++.h> using namespace std; const int MAXN = int( 1e5 ); const int MAXQ = int( 1e5 ); int N, Q; int A[ MAXN ]; vector< int > G[ MAXN ]; int dpt[ MAXN ]; int par[ MAXN ][ 20 ]; void dfs_dpt( int u, int fa, int d ) { dpt[ u ] = d + 1; par[ u ][ 0 ] = fa; for( int v : G[ u ] ) { if( v == fa ) continue; dfs_dpt( v, u, d + 1 ); } } int lca( int u, int v ) { if( not ( dpt[ u ] >= dpt[ v ] ) ) { swap( u, v ); } int diff = dpt[ u ] - dpt[ v ]; for( int i = 20 - 1; diff; --i ) { if( diff >= 1 << i ) { diff -= 1 << i; u = par[ u ][ i ]; } } if( u == v ) return u; for( int i = 20 - 1; par[ u ][ 0 ] != par[ v ][ 0 ]; --i ) { if( par[ u ][ i ] != par[ v ][ i ] ) { u = par[ u ][ i ]; v = par[ v ][ i ]; } } return par[ u ][ 0 ]; } int st[ MAXN ], ed[ MAXN ]; int flat[ MAXN * 2 ]; void dfs_flat( int u, int fa ) { static int ts = 0; st[ u ] = ts; flat[ ts++ ] = u; for( int v : G[ u ] ) { if( v == fa ) continue; dfs_flat( v, u ); } ed[ u ] = ts; flat[ ts++ ] = u; } struct trie { trie *ch[ 2 ]; int cnt[ 2 ]; trie() { ch[ 0 ] = ch[ 1 ] = NULL; cnt[ 0 ] = cnt[ 1 ] = 0; } }; void add( trie *root, int x, int v, int t = 30 ) { if( t == -1 ) return; int k = x >> t & 1; if( root->ch[ k ] == NULL ) { root->ch[ k ] = new trie(); } root->cnt[ k ] += v; add( root->ch[ k ], x, v, t - 1 ); } int get_max( trie *root, int x, int t = 30 ) { if( t == -1 ) return 0; int k = x >> t & 1; if( root->ch[ k ^ 1 ] and root->cnt[ k ^ 1 ] ) { return ( 1 << t ) + get_max( root->ch[ k ^ 1 ], x, t - 1 ); } return get_max( root->ch[ k ], x, t - 1 ); } int ans[ MAXQ ]; vector< tuple< int, int, int, int > > qry; void print( trie *root, int v = 0, int t = 30 ) { if( t < 0 ) { cout << v << endl; return; } if( root->ch[ 0 ] and root->cnt[ 0 ] ) { print( root->ch[ 0 ], v, t - 1 ); } if( root->ch[ 1 ] and root->cnt[ 1 ] ) { print( root->ch[ 1 ], ( 1 << t ) + v, t - 1 ); } } signed main() { ios::sync_with_stdio( 0 ); cin >> N >> Q; for( int i = 0; i < N; ++i ) { cin >> A[ i ]; } for( int i = 0; i < N - 1; ++i ) { int u, v; cin >> u >> v; --u, --v; G[ u ].emplace_back( v ); G[ v ].emplace_back( u ); } dfs_dpt( 0, -1, 0 ); for( int j = 0; j + 1 < 20; ++j ) { for( int i = 0; i < N; ++i ) { int m = par[ i ][ j ]; if( m == -1 ) continue; par[ i ][ j + 1 ] = par[ m ][ j ]; } } dfs_flat( 0, -1 ); for( int qi = 0; qi < Q; ++qi ) { int u, v; cin >> u >> v; --u, --v; if( not ( st[ u ] <= st[ v ] ) ) { swap( u, v ); } int p = lca( u, v ); if( p == u ) { qry.emplace_back( A[ u ], st[ u ], st[ v ], qi ); qry.emplace_back( A[ v ], st[ u ], st[ v ], qi ); } else { ans[ qi ] = max( A[ u ] ^ A[ p ], A[ v ] ^ A[ p ] ); qry.emplace_back( A[ u ], ed[ u ], st[ v ], qi ); qry.emplace_back( A[ v ], ed[ u ], st[ v ], qi ); } } const int MAGIC = 300; sort( qry.begin(), qry.end(), [ & ]( tuple< int, int, int, int > i, tuple< int, int, int, int > j ) { if( get< 1 >( i ) / MAGIC != get< 1 >( j ) / MAGIC ) return get< 1 >( i ) / MAGIC < get< 1 >( j ) / MAGIC; return get< 2 >( i ) < get< 2 >( j ); } ); for( int i = 0, lb = 1, rb = 0; i < qry.size(); ++i ) { static trie *root = new trie(); static int vis[ MAXN * 2 ]; int x, ql, qr, id; tie( x, ql, qr, id ) = qry[ i ]; while( lb < ql ) { add( root, A[ flat[ lb ] ], ( ++vis[ flat[ lb ] ] & 1 ) ? 1 : -1 ); ++lb; } while( ql < lb ) { --lb; add( root, A[ flat[ lb ] ], ( ++vis[ flat[ lb ] ] & 1 ) ? 1 : -1 ); } while( rb < qr ) { ++rb; add( root, A[ flat[ rb ] ], ( ++vis[ flat[ rb ] ] & 1 ) ? 1 : -1 ); } while( qr < rb ) { add( root, A[ flat[ rb ] ], ( ++vis[ flat[ rb ] ] & 1 ) ? 1 : -1 ); --rb; } ans[ id ] = max( ans[ id ], get_max( root, x ) ); } for( int i = 0; i < Q; ++i ) { cout << ans[ i ] << "\n"; } return 0; }
_
// Persistent Trie #include <bits/stdc++.h> using namespace std; const int MAXN = int( 1e5 ); const int MAXQ = int( 1e5 ); int N, Q; int A[ MAXN ]; vector< int > G[ MAXN ]; int dpt[ MAXN ]; int par[ MAXN ][ 20 ]; void dfs_dpt( int u, int fa, int d ) { dpt[ u ] = d + 1; par[ u ][ 0 ] = fa; for( int v : G[ u ] ) { if( v == fa ) continue; dfs_dpt( v, u, d + 1 ); } } int lca( int u, int v ) { if( not ( dpt[ u ] >= dpt[ v ] ) ) { swap( u, v ); } int diff = dpt[ u ] - dpt[ v ]; for( int i = 20 - 1; diff; --i ) { if( diff >= 1 << i ) { diff -= 1 << i; u = par[ u ][ i ]; } } if( u == v ) return u; for( int i = 20 - 1; par[ u ][ 0 ] != par[ v ][ 0 ]; --i ) { if( par[ u ][ i ] != par[ v ][ i ] ) { u = par[ u ][ i ]; v = par[ v ][ i ]; } } return par[ u ][ 0 ]; } struct trie { trie *ch[ 2 ]; int cnt[ 2 ]; trie() { ch[ 0 ] = ch[ 1 ] = NULL; cnt[ 0 ] = cnt[ 1 ] = 0; } } *troot[ MAXN ]; trie* clone( trie *t ) { trie *res = new trie(); if( not t ) return res; for( int i = 0; i < 2; ++i ) { res->ch[ i ] = t->ch[ i ]; res->cnt[ i ] = t->cnt[ i ]; } return res; } trie* add( trie *root, int x, int v, int t = 30 ) { if( t == -1 ) return NULL; int k = x >> t & 1; trie *res = clone( root ); if( res->ch[ k ] == NULL ) { res->ch[ k ] = new trie(); } res->cnt[ k ] += v; res->ch[ k ] = add( root ? root->ch[ k ] : NULL, x, v, t - 1 ); return res; } int get_max( int x, trie *a, trie *b, trie *c, trie *d, int t ) { // a + b - c - d if( t == -1 ) return 0; int k = x >> t & 1; int cnt = ( a ? a->cnt[ k ^ 1 ] : 0 ) + ( b ? b->cnt[ k ^ 1 ] : 0 ) - ( c ? c->cnt[ k ^ 1 ] : 0 ) - ( d ? d->cnt[ k ^ 1 ] : 0 ); if( cnt ) { return ( 1 << t ) + get_max( x, ( a ? a->ch[ k ^ 1 ] : NULL ), ( b ? b->ch[ k ^ 1 ] : NULL ), ( c ? c->ch[ k ^ 1 ] : NULL ), ( d ? d->ch[ k ^ 1 ] : NULL ), t - 1 ); } return get_max( x, ( a ? a->ch[ k ] : NULL ), ( b ? b->ch[ k ] : NULL ), ( c ? c->ch[ k ] : NULL ), ( d ? d->ch[ k ] : NULL ), t - 1 ); } void dfs_construct_trie( int u, int fa, trie *p ) { troot[ u ] = add( p, A[ u ], 1 ); for( int v : G[ u ] ) { if( v == fa ) continue; dfs_construct_trie( v, u, troot[ u ] ); } } signed main() { ios::sync_with_stdio( 0 ); cin >> N >> Q; for( int i = 0; i < N; ++i ) { cin >> A[ i ]; } for( int i = 0; i < N - 1; ++i ) { int u, v; cin >> u >> v; --u, --v; G[ u ].emplace_back( v ); G[ v ].emplace_back( u ); } dfs_dpt( 0, -1, 0 ); for( int j = 0; j + 1 < 20; ++j ) { for( int i = 0; i < N; ++i ) { int m = par[ i ][ j ]; if( m == -1 ) continue; par[ i ][ j + 1 ] = par[ m ][ j ]; } } dfs_construct_trie( 0, -1, NULL ); for( int qi = 0; qi < Q; ++qi ) { int u, v; cin >> u >> v; --u, --v; int p = lca( u, v ); if( p == v ) { cout << max( { A[ u ] ^ A[ v ], get_max( A[ u ], troot[ u ], NULL, troot[ v ], NULL, 30 ), get_max( A[ v ], troot[ u ], NULL, troot[ v ], NULL, 30 ) } ) << "\n"; } else if( p == u ) { cout << max( { A[ u ] ^ A[ v ], get_max( A[ u ], troot[ v ], NULL, troot[ u ], NULL, 30 ), get_max( A[ v ], troot[ v ], NULL, troot[ u ], NULL, 30 ) } ) << "\n"; } else { cout << max( { A[ u ] ^ A[ p ], A[ v ] ^ A[ p ], get_max( A[ u ], troot[ u ], troot[ v ], troot[ p ], troot[ p ], 30 ), get_max( A[ v ], troot[ u ], troot[ v ], troot[ p ], troot[ p ], 30 ) } ) << "\n"; } } return 0; }