結果
問題 | No.2163 LCA Sum Query |
ユーザー | 👑 p-adic |
提出日時 | 2022-12-16 23:43:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 18,461 bytes |
コンパイル時間 | 4,576 ms |
コンパイル使用メモリ | 265,576 KB |
実行使用メモリ | 94,660 KB |
最終ジャッジ日時 | 2024-04-27 22:43:48 |
合計ジャッジ時間 | 29,810 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,180 KB |
testcase_01 | AC | 4 ms
8,044 KB |
testcase_02 | AC | 10 ms
8,308 KB |
testcase_03 | AC | 9 ms
8,340 KB |
testcase_04 | AC | 9 ms
8,236 KB |
testcase_05 | AC | 9 ms
8,200 KB |
testcase_06 | AC | 6 ms
8,308 KB |
testcase_07 | AC | 5 ms
8,184 KB |
testcase_08 | AC | 7 ms
8,568 KB |
testcase_09 | AC | 9 ms
8,376 KB |
testcase_10 | AC | 14 ms
9,336 KB |
testcase_11 | AC | 8 ms
8,436 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 611 ms
8,648 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 1,381 ms
10,672 KB |
testcase_19 | AC | 936 ms
8,872 KB |
testcase_20 | AC | 338 ms
22,320 KB |
testcase_21 | WA | - |
testcase_22 | TLE | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/c++allocator.h:33, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/allocator.h:46, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:41, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54, from main.cpp:4: In member function 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = std::_List_node<int>]', inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = std::_List_node<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/alloc_traits.h:516:17, inlined from 'std::__cxx11::list<_Tp, _Alloc>::_Node* std::__cxx11::list<_Tp, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {const int&}; _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_list.h:713:33, inlined from 'void std::__cxx11::list<_Tp, _Alloc>::_M_insert(iterator, _Args&& ...) [with _Arg
ソースコード
// #define _GLIBCXX_DEBUG #pragma GCC optimize ( "O3" ) #pragma GCC target ( "avx" ) #include <bits/stdc++.h> using namespace std; using uint = unsigned int; using ll = long long; #define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 // #define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; #define COUT( ANSWER ) cout << ( ANSWER ) << endl; #define RETURN( ANSWER ) COUT( ANSWER ); QUIT #define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT #define POWER( ANSWER , ARGUMENT , EXPONENT ) \ TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \ { \ TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ #define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \ TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \ { \ TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ #define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO ) \ ll ANSWER[LENGTH]; \ ll ANSWER_INV[LENGTH]; \ { \ ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \ ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \ FOREQ( i , 1 , MAX_I ){ \ ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \ } \ POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \ ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV; \ FOREQINV( i , MAX_I - 1 , 0 ){ \ ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO; \ } \ } \ \ // 通常の二分探索 #define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER = MAXIMUM; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \ } else { \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ \ // 二進法の二分探索 #define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER = MINIMUM; \ { \ ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \ while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2; \ } \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \ ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \ while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){ \ ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \ break; \ } else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \ } \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \ } \ ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2; \ } \ \ template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; } template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; } #define first1 first.first #define second1 first.second #define third1 second #define first2 first1 #define second2 second1 #define third2 second.first #define fourth2 second.second inline CEXPR( int , bound_N , 50000 ); // lazy_segtree用のデータ1 using S1 = pair<pair<int,int>,ll>; inline S1 op1( S1 a , S1 b ) { return S1( pair<int,int>( a.first1 + b.first1 , a.second1 + b.second1 ) , a.third1 + b.third1 ); } inline S1 unit1() { return S1(); } using F1 = int; // vが(A,Ax,Ax^2)の形のベクトルの時にfvが(A,A(x+f),A(x+f)^2)=(A,Ax+fA,Ax^2+2fAx+f^2A)となるようなモノイド作用 inline S1 act1( F1 f , S1 v ) { return S1( pair<int,int>( v.first1 , v.second1 + f * v.first1 ) , v.third1 + ( f * 2 ) * v.second1 + ( f * f ) * v.first1 ); } inline F1 comp1( F1 f1 , F1 f2 ) { return f1 + f2; } inline F1 id1() { return 0; } // lazy_segtree用のデータ2 using S2 = pair<pair<int,int>,pair<int,ll> >; inline S2 op2( S2 a , S2 b ) { return S2( pair<int,int>( a.first2 + b.first2 , a.second2 + b.second2 ) , pair<int,ll>( a.third2 + b.third2 , a.fourth2 + b.fourth2 ) ); } inline S2 unit2() { return S2(); } using F2 = pair<int,int>; // vが(A,Ax,Ay,Axy)の形のベクトルの時に(f_1,f_2)vが(A,A(x+f_1),A(y+f_2),A(x+f_1)(y+f_2))=(A,Ax+f_1A,Ay+f_2A,Axy+f_1Ay+f_2Ax+f_1f_2A)となるようなモノイド作用 inline S2 act2( F2 f , S2 v ) { return S2( pair<int,int>( v.first2 , v.second2 + f.first * v.first2 ) , pair<int,ll>( v.third2 + f.second * v.first2 , v.fourth2 + f.first * v.third2 + f.second * v.second2 + ( f.first * f.second ) * v.first2 ) ); } inline F2 comp2( F2 f1 , F2 f2 ) { return F2( f1.first + f2.first , f1.second + f2.second ); } inline F2 id2() { return F2(); } // lazy_segtree用のデータ3 using S3 = int; inline S3 op3( S3 a , S3 b ) { return a + b; } inline S3 unit3() { return 0; } using F3 = int; inline S3 act3( F3 f , S3 v ) { return f + v; } inline F3 comp3( F3 f1 , F3 f2 ) { return f1 + f2; } inline F3 id3() { return 0; } using Interval = pair<int,int>; #include <atcoder/lazysegtree> using namespace atcoder; // Xの総和を計算するための、部分木におけるS内の総和の計算 inline int sum( int v , int ( &HL_inv )[bound_N+1] , list<Interval> ( &descendant )[bound_N] , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 ) { list<Interval>& descendant_v = descendant[HL_inv[v]]; int answer = 0; FOR_ITR( descendant_v , itr_v , end_v ){ Interval& descendant_vj = *itr_v; answer += v3.prod( descendant_vj.first , descendant_vj.second + 1 ); } return answer; } // 解説におけるf(1,v)の計算 inline ll f1v( int v , int ( &parent )[bound_N+1] , int ( &HL_inv )[bound_N+1] , list<Interval> ( &descendant )[bound_N] , lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1>& v1 , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 ) { int& parent_v = parent[v]; int& HL_inv_v = HL_inv[v]; list<Interval>& descendant_v = descendant[HL_inv_v]; ll answer = 0; FOR_ITR( descendant_v , itr_v , end_v ){ Interval& descendant_vj = *itr_v; // 解説ではvの親に言及しているため暗にv != 1を課しているが、ここではrootの親を便宜上0とすることで場合分けを回避 answer += v1.prod( descendant_vj.first , descendant_vj.second + 1 ).third1; } // 解説におけるXの総和は(Ri,Vi)を(1,v)に置き換えてXを定義し直した時の値であることに注意。 // 特に(Ri,Vi)=(v,v)!=(1,1)の時のf(v,v)(v!=1)の計算で呼び出されるf(1,1)の計算で参照されるXは問題文中で定義された集合とは別物であり(Ri,Vi)=(1,1)に置き換えて定義し直したものとなる。 answer -= sum( v , HL_inv , descendant , v3 ); answer += ( v1.prod( HL_inv_v , HL_inv_v + 1 ).third1 / ( v - parent_v ) ) * parent_v; answer /= 2; return answer; } // 解説におけるf(v,v)の計算 inline ll fvv( int v , int ( &parent )[bound_N+1] , int ( &HL_inv )[bound_N+1] , list<Interval> ( &descendant )[bound_N] , list<Interval> ( &path )[bound_N] , lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1>& v1 , lazy_segtree<S2,op2,unit2,F2,act2,comp2,id2>& v2 , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 ) { ll answer = f1v( 1 , parent , HL_inv , descendant , v1 , v3 ); list<Interval>& path_v = path[HL_inv[v]]; FOR_ITR( path_v , itr_v , end_v ){ // |S|-c(root,root) = 0であるので本来不要なrootの寄与は自動的に消える answer += v2.prod( itr_v->first , itr_v->second + 1 ).fourth2; } return answer; } int main() { UNTIE; CIN_ASSERT( N , 1 , bound_N ); CEXPR( int , bound_Q , 100000 ); CIN_ASSERT( Q , 1 , bound_Q ); // 一旦子と親を全て同じ配列に格納 list<int> children[bound_N+1] = {}; FOR( i , 1 , N ){ CIN_ASSERT( Ai , 1 , N ); CIN_ASSERT( Bi , 1 , N ); assert( Ai != Bi ); children[Ai].push_back( Bi ); children[Bi].push_back( Ai ); } // 子と親の決定 int parent[bound_N+1]; parent[1] = 0; list<int> layer[bound_N] = {}; int children_query[bound_N]; children_query[0] = 1; int start_children_query = 0; int size_children_query = 1; int size_children_query_copy = size_children_query; int depth = 0; while( start_children_query < size_children_query ){ list<int>& layer_curr = layer[depth]; FOR( i , start_children_query , size_children_query ){ int& children_query_i = children_query[i]; layer_curr.push_back( children_query_i ); list<int>& children_i = children[children_query_i]; FOR_ITR( children_i , itr_i , end_i ){ int& j = *itr_i; parent[j] = children_query_i; list<int>& children_ij = children[j]; FOR_ITR( children_ij , itr_ij , end_ij ){ if( children_query_i == *itr_ij ){ children_ij.erase( itr_ij ); break; } } children_query[size_children_query_copy++] = j; } } depth++; start_children_query = size_children_query; size_children_query = size_children_query_copy; } // HL分解のための重さ計算 int weight[bound_N + 1]; FOREQINV( d , depth - 1 , 0 ){ list<int>& layer_curr = layer[d]; FOR_ITR( layer_curr , itr_d , end_d ){ int& i = *itr_d; list<int>& children_curr = children[i]; int& weight_i = weight[i]; weight_i = 1; FOR_ITR( children_curr , itr_i , end_i ){ weight_i += weight[*itr_i]; } } } // HL分解のためのheight計算 int children_H_i; int weight_max; FOREQ( i , 1 , N ){ list<int>& children_i = children[i]; weight_max = -1; FOR_ITR( children_i , itr , end ){ int& j_curr = *itr; int& weight_j_curr = weight[j_curr]; if( weight_max < weight_j_curr ){ weight_max = weight_j_curr; children_H_i = j_curr; } } FOR_ITR( children_i , itr , end ){ if( children_H_i == *itr ){ children_i.erase( itr ); children_i.push_front( children_H_i ); break; } } } // HL分解(添え字は0始まり、葉に小さい番号づけ) int HL[bound_N]; int HL_inv[bound_N+1]; list<int> vertex_stack{}; list<int> root{ { 1 } }; list<list<int>::iterator> children_itr_stack{}; children_itr_stack.push_back( root.begin() ); list<list<int>::iterator> children_end_stack{}; children_end_stack.push_back( root.end() ); int length = 0; while( ! children_itr_stack.empty() ){ list<int>::iterator& itr_curr = children_itr_stack.back(); list<int>::iterator& end_curr = children_end_stack.back(); if( itr_curr == end_curr ){ children_itr_stack.pop_back(); children_end_stack.pop_back(); } else { int& i_curr = *itr_curr; list<int>& children_curr = children[i_curr]; auto itr_new = children_curr.begin() , end_new = children_curr.end(); if( itr_new == end_new ){ HL_inv[i_curr] = length; HL[length++] = i_curr; FOR_ITR( vertex_stack , itr_v , end_v ){ int& i_prev = *itr_v; HL_inv[i_prev] = length; HL[length++] = i_prev; } vertex_stack.clear(); } else { vertex_stack.push_front( i_curr ); children_itr_stack.push_back( itr_new ); children_end_stack.push_back( end_new ); } itr_curr++; } } // 1からのパス計算(ここが各ノードでlogオーダーになることがHL分解特有の事情) int& HL_inv_root = HL_inv[1]; list<Interval> path[bound_N]; path[HL_inv_root] = list<Interval>( { Interval( HL_inv_root , HL_inv_root ) } ); FOR( d , 1 , depth ){ list<int>& layer_curr = layer[d]; FOR_ITR( layer_curr , itr_d , end_d ){ int& i = *itr_d; int& parent_i = parent[i]; int& HL_inv_parent_i = HL_inv[parent_i]; int& HL_inv_i = HL_inv[i]; list<Interval>& path_parent_i = path[HL_inv_parent_i]; list<Interval>& path_i = path[HL_inv_i]; path_i = path_parent_i; if( children[parent_i].front() == i ){ path_i.back().first = HL_inv_i; } else { path_i.push_back( Interval( HL_inv_i , HL_inv_i ) ); } } } // ノードの子孫のなすHL上の区間続の決定(メモ:もしTLEしたらここを改善すべき) list<Interval> descendant[bound_N]; FOREQINV( d , depth - 1 , 0 ){ list<int>& layer_curr = layer[d]; FOR_ITR( layer_curr , itr_d , end_d ){ int& i = *itr_d; list<int>& children_curr = children[i]; int& HL_inv_i = HL_inv[i]; list<Interval>& descendant_i = descendant[HL_inv_i]; if( children_curr.empty() ){ descendant_i.push_back( Interval( HL_inv_i , HL_inv_i ) ); } else { auto itr_i = children_curr.begin() , end_i = children_curr.end(); descendant_i = descendant[HL_inv[*itr_i]]; descendant_i.front().second = HL_inv_i; while( ++itr_i != end_i ){ list<Interval>& descendant_j = descendant[HL_inv[*itr_i]]; FOR_ITR( descendant_j , itr_j , end_j ){ descendant_i.push_back( *itr_j ); } } } } } // 解説における(x-(xの親),(x-(xの親))c(1,x),(x-(xの親))c(1,x)^2)の管理 lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1> v1{ N }; FOR( i , 0 , N ){ int& HL_i = HL[i]; v1.set( i , S1( pair<int,int>( HL_i - parent[HL_i] , 0 ) , 0 ) ); } // 解説における(x-(xの親),(x-(xの親))c(1,x),(x-(xの親))(|S|-c(1,x)),(x-(xの親))c(1,x)(|S|-c(1,x)))の管理 lazy_segtree<S2,op2,unit2,F2,act2,comp2,id2> v2{ N }; FOR( i , 0 , N ){ int& HL_i = HL[i]; v2.set( i , S2( pair<int,int>( HL_i - parent[HL_i] , 0 ) , pair<int,ll>( 0 , 0 ) ) ); } // Xの総和を計算するための(x in S ? x : 0)の管理 lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3> v3{ N }; set<int> S{}; int sign , x , HL_inv_x; bool belong; // クエリ処理 REPEAT( Q ){ CIN_ASSERT( Ui , 1 , N ); CIN_ASSERT( Ri , 1 , N ); CIN_ASSERT( Vi , 1 , N ); if( S.count( Ui ) == 0 ){ sign = 1; S.insert( Ui ); } else { sign = -1; S.erase( Ui ); } int& HL_inv_Ui = HL_inv[Ui]; v3.apply( HL_inv_Ui , HL_inv_Ui + 1, sign * Ui ); v2.apply( 0 , N , F2( 0 , sign ) ); list<Interval>& path_Ui = path[HL_inv[Ui]]; FOR_ITR( path_Ui , itr_i , end_i ){ Interval& path_Uij = *itr_i; v1.apply( path_Uij.first , path_Uij.second + 1 , sign ); v2.apply( path_Uij.first , path_Uij.second + 1 , F2( sign , -sign ) ); } int& HL_inv_Vi = HL_inv[Vi]; list<Interval>& descendant_Vi = descendant[HL_inv_Vi]; if( Ri == Vi ){ COUT( fvv( Vi , parent , HL_inv , descendant , path , v1 , v2 , v3 ) ); } else { int& HL_inv_Ri = HL_inv[Ri]; belong = false; FOR_ITR( descendant_Vi , itr_i , end_i ){ Interval& descendant_Vij = *itr_i; if( descendant_Vij.first <= HL_inv_Ri && HL_inv_Ri <= descendant_Vij.second ){ belong = true; break; } } if( belong ){ list<Interval>& path_Ri = path[HL_inv_Ri]; FOR_ITR( path_Ri , itr_Ri , end_Ri ){ Interval& path_Rij = *itr_Ri; if( path_Rij.first <= HL_inv_Vi && HL_inv_Vi <= path_Rij.second ){ if( path_Rij.first == HL_inv_Vi ){ itr_Ri++; HL_inv_x = itr_Ri->second; } else { HL_inv_x = HL_inv_Vi - 1; } x = HL[HL_inv_x]; COUT( fvv( Vi , parent , HL_inv , descendant , path , v1 , v2 , v3 ) - f1v( x , parent , HL_inv , descendant , v1 , v3 ) - ( v2.prod( HL_inv_x , HL_inv_x + 1 ).fourth2 / ( x - Vi ) ) * Vi ); break; } } } else { COUT( f1v( Vi , parent , HL_inv , descendant , v1 , v3 )); } } } QUIT; }