#ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE // #define USE_GETLINE #endif #ifdef INCLUDE_MAIN IN VO Solve() { CIN( int , N ); CIN_A( int , A , N ); FOR( i , 0 , N ){ A[i]--; } CIN( int , Q ); Trop<>::SetZero( -1e5 ); using U = Matrix<4,4,Trop<>>; U E; FOR( i , 0 , 4 ){ FOR( j , i , 4 ){ E[i][j] = 0; } } vector M = { E , E , E , E }; FOR( i , 0 , 4 ){ FOR( j , i , 4 ){ M[i][i][j] = 1; } } auto UPower = [&]( const int& i , U a ){ int exponent = i; U answer{ E }; while( exponent > 0 ){ ( exponent & 1 ) == 1 ? answer *= a : answer; a *= a; exponent >>= 1; } return answer; }; IntervalSetSqrtDecomposition sd{ AbstractModule( 0 , UPower , MultiplicativeMonoid( E ) ) };{ vector init( N ); FOR( i , 0 , N ){ init[i] = M[A[i]]; } sd.Initialise( move( init ) ); } FOR( q , 0 , Q ){ CIN( int , type ); if( type == 1 ){ CIN( ll , x , y ); x--; y--; auto a = sd.IntervalProduct( x , y ); Trop<> answer = 0; FOR( i , 0 , 4 ){ answer += a[i][3]; } COUT( answer.Get() ); } else if( type == 2 ){ CIN( ll , x , y , n ); x--; y--; sd.IntervalSet( x , y , M[--n] ); } } } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_SUB // 圧縮時は中身だけ削除する。 IN VO Experiment() { } // 圧縮時は中身だけ削除する。 IN VO SmallTest() { } // 圧縮時は中身だけ削除する。 IN VO RandomTest() { } #define INCLUDE_MAIN #include __FILE__ #else // INCLUDE_SUB #ifdef INCLUDE_LIBRARY // VVV 常設でないライブラリは以下に挿入する。 TE CL Trop;TE CL ZeroForTrop{PU:ZeroForTrop()= delete;ST U g_zero;};TE CL Trop{PU:U m_n;IN Trop(CO U& n = ZeroForTrop::g_zero);IN Trop& OP+=(CO Trop& n);IN Trop& OP*=(CO Trop& n);IN Trop OP+(CO Trop& n)CO;IN Trop OP*(CO Trop& n)CO;IN VO Set(CO U& n)NE;IN CO U& Get()CO NE;ST IN VO SetZero(CO U& zero)NE;;}; TE U ZeroForTrop::g_zero{};TE IN Trop::Trop(CO U& n):m_n(n){}TE IN Trop& Trop::OP+=(CO Trop& n){n.m_n == ZeroForTrop::g_zero?m_n:m_n =(m_n == ZeroForTrop::g_zero?n.m_n:max(m_n,n.m_n));RE *TH;}TE IN Trop& Trop::OP*=(CO Trop& n){m_n == ZeroForTrop::g_zero?m_n:m_n =(n.m_n == ZeroForTrop::g_zero?ZeroForTrop::g_zero:m_n + n.m_n);RE *TH;}TE IN Trop Trop::OP+(CO Trop& n)CO{RE MO(Trop(*TH)+= n);}TE IN Trop Trop::OP*(CO Trop& n)CO{RE MO(Trop(*TH)*= n);}TE IN VO Trop::Set(CO U& n)NE{m_n = n;}TE IN CO U& Trop::Get()CO NE{RE m_n;}TE IN VO Trop::SetZero(CO U& zero)NE{ZeroForTrop::g_zero = zero;};TE IN basic_istream& OP>>(basic_ostream& is,CO Trop& n)NE{U temp;is >> temp;n.Set(temp);RE is;}TE IN basic_ostream& OP<<(basic_ostream& os,CO Trop& n)NE{RE os << n.Get();} #define MA Matrix #define SFINAE_FOR_MA(DEFAULT) TY Arg,enable_if_t::value>* DEFAULT TE CL MA{PU:T m_M[Y][X];IN MA()NE;IN MA(CO T& t)NE;IN MA(CRI t)NE;TE IN MA(Arg0&& t0,Arg1&& t1,Args&&... args)NE;IN MA(CO MA& mat)NE;IN MA(MA&& mat)NE;TE IN MA(CO T (&mat)[Y][X])NE;TE IN MA(T (&&mat)[Y][X])NE;IN MA& OP=(CO MA& mat)NE;IN MA& OP=(MA&& mat)NE;IN MA& OP=(CO T (&mat)[Y][X])NE;IN MA& OP=(T (&&mat)[Y][X])NE;IN MA& OP+=(CO MA& mat)NE;IN MA& OP-=(CO MA& mat)NE;IN MA& OP*=(CO T& scalar)NE;IN MA& OP*=(CO MA& mat)NE;IN MA& OP/=(CO T& scalar);IN MA& OP%=(CO T& scalar);IN bool OP==(CO MA& mat) CO NE;TE IN MA OP*(CO MA& mat) CO NE;IN MA Transpose() CO NE;IN T Trace() CO NE;IN CO T(&OP[](CRUI y)CO)[X];IN T(&OP[](CRUI y))[X];ST IN CO MA& Zero()NE;ST IN CO MA& One()NE;ST IN VO SetArray(T (&M)[Y][X],T (&&array)[Y * X])NE;}; TE IN MA::MA()NE:m_M(){}TE IN MA::MA(CO T& t)NE:m_M(){CE CO uint minXY = Y < X?Y:X;for(uint y = 0;y < minXY;y++){m_M[y][y] = t;}}TE IN MA::MA(CRI t)NE:MA(T(t)){}TE TE IN MA::MA(Arg0&& t0,Arg1&& t1,Args&&... args)NE:m_M(){T array[Y * X] ={T(forward(t0)),T(forward(t1)),T(forward(args))...};SetArray(m_M,MO(array));}TE IN MA::MA(CO MA& mat)NE:m_M(){OP=(mat.m_M);}TE IN MA::MA(MA&& mat)NE:m_M(){swap(m_M,mat.m_M);}TE TE IN MA::MA(CO T (&mat)[Y][X])NE:m_M(){OP=(mat);}TE TE IN MA::MA(T (&&mat)[Y][X])NE:m_M(){swap(m_M,mat);}TE IN MA& MA::OP=(CO MA& mat)NE{RE OP=(mat.m_M);}TE IN MA& MA::OP=(MA&& mat)NE{RE OP=(MO(mat.m_M));}TE IN MA& MA::OP=(CO T (&mat)[Y][X])NE{for(uint y = 0;y < Y;y++){T (&m_M_y)[X] = m_M[y];CO T (&mat_y)[X] = mat[y];for(uint x = 0;x < X;x++){m_M_y[x] = mat_y[x];}}RE *TH;}TE IN MA& MA::OP=(T (&&mat)[Y][X])NE{swap(m_M,mat);RE *TH;}TE IN MA& MA::OP+=(CO MA& mat)NE{for(uint y = 0;y < Y;y++){T (&m_M_y)[X] = m_M[y];T (&mat_y)[X] = mat.m_M[y];for(uint x = 0;x < X;x++){m_M_y[x] += mat_y[x];}}RE *TH;}TE IN MA& MA::OP-=(CO MA& mat)NE{for(uint y = 0;y < Y;y++){T (&m_M_y)[X] = m_M[y];T (&mat_y)[X] = mat.m_M[y];for(uint x = 0;x < X;x++){m_M_y[x] -= mat_y[x];}}RE *TH;}TE IN MA& MA::OP*=(CO T& scalar)NE{for(uint y = 0;y < Y;y++){T (&m_M_y)[X] = m_M[y];for(uint x = 0;x < X;x++){m_M_y[x] *= scalar;}}RE *TH;}TE IN MA& MA::OP*=(CO MA& mat)NE{RE OP=(MO(*TH * mat));}TE IN MA& MA::OP/=(CO T& scalar){RE OP*=(T(1) / scalar);}TE IN MA& MA::OP%=(CO T& scalar){for(uint y = 0;y < Y;y++){T (&m_M_y)[X] = m_M[y];for(uint x = 0;x < X;x++){m_M_y[x] %= scalar;}}RE *TH;}TE TE IN MA MA::OP*(CO MA& mat) CO NE{MA prod{};for(uint y = 0;y < Y;y++){CO T (&m_M_y)[X] = m_M[y];T (&prod_y)[Z] = prod.m_M[y];for(uint x = 0;x < X;x++){CO T &m_M_yx = m_M_y[x];CO T (&mat_x)[Z] = mat.m_M[x];for(uint z = 0;z < Z;z++){prod_y[z] += m_M_yx * mat_x[z];}}}RE prod;}TE IN bool MA::OP==(CO MA& mat) CO NE{for(uint y = 0;y < Y;y++){CO T (&m_M_y)[X] = m_M[y];CO T (&mat_y)[X] = mat[y];for(uint x = 0;x < X;x++){if(m_M_y[x] != mat_y[x]){RE false;}}}RE true;}TE IN MA MA::Transpose() CO NE{MA M_t{};for(uint x = 0;x < X;x++){CO T (&M_t_x)[Y] = M_t.m_M[x];for(uint y = 0;y < Y;y++){M_t_x[y] = m_M[y][x];}}RE M_t;}TE IN T MA::Trace() CO NE{CE CO uint minXY = Y < X?Y:X;T AN{};for(uint y = 0;y < minXY;y++){AN += m_M[y][y];}RE AN;}TE IN CO T(&MA::OP[](CRUI y)CO)[X]{AS(y < Y);RE m_M[y];}TE IN T(&MA::OP[](CRUI y))[X]{AS(y < Y);RE m_M[y];}TE IN CO MA& MA::Zero()NE{ST CO MA zero{};RE zero;}TE IN CO MA& MA::One()NE{ST CO MA one{1};RE one;}TE IN VO MA::SetArray(T (&M)[Y][X],T (&&array)[Y * X])NE{uint i = 0;for(uint y = 0;y < Y;y++){T (&M_y)[X] = M[y];for(uint x = 0;x < X;x++){M_y[x] = MO(array[i + x]);}i += X;}}TE IN MA OP!=(CO MA& mat1,CO MA& mat2)NE{RE !(mat1 == mat2);}TE IN MA OP+(CO MA& mat1,CO MA& mat2)NE{RE MO(MA(mat1) += mat2);}TE IN MA OP-(CO MA& mat1,CO MA& mat2)NE{RE MO(MA(mat1) -= mat2);}TE IN MA OP*(CO MA& mat,CO T& scalar)NE{RE MO(MA(mat) *= scalar);}TE IN MA OP*(CO T& scalar,CO MA& mat)NE{RE MO(MA(mat) *= scalar);}TE IN MA OP/(CO MA& mat,CO T& scalar){RE MO(MA(mat) /= scalar);}TE IN MA OP%(CO MA& mat,CO T& scalar){RE MO(MA(mat) %= scalar);} TE CL VirtualRSet:VI PU UnderlyingSet{PU:VI U Action(CO R& r,U u)= 0;IN U PW(U u,CO R& r);IN U ScalarProduct(CO R& r,U u);};TE CL RegularRSet:VI PU VirtualRSet,PU MAGMA{PU:IN RegularRSet(MAGMA magma);IN U Action(CO U& r,U u);};TE RegularRSet(MAGMA magma)-> RegularRSet,MAGMA>;TE CL AbstractRSet:VI PU VirtualRSet{PU:O_U m_o_U;IN AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U);IN U Action(CO R& r,U u);};TE CL AbstractModule:PU AbstractRSet,PU GROUP{PU:IN AbstractModule(CO R& dummy,O_U o_U,GROUP M);};TE AbstractModule(CO R& dummy,O_U o_U,GROUP M)-> AbstractModule,O_U,GROUP>;TE CL Module:VI PU VirtualRSet,PU AdditiveGroup{PU:IN U Action(CO R& r,U u);}; TE IN RegularRSet::RegularRSet(MAGMA magma):MAGMA(MO(magma)){}TE IN AbstractRSet::AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U):m_o_U(MO(o_U)){ST_AS(is_invocable_r_v);}TE IN AbstractModule::AbstractModule(CO R& dummy,O_U o_U,GROUP M):AbstractRSet(dummy,M.One(),MO(o_U)),GROUP(MO(M)){ST_AS(is_same_v>);}TE IN U RegularRSet::Action(CO U& r,U u){RE TH->Product(r,MO(u));}TE IN U AbstractRSet::Action(CO R& r,U u){RE m_o_U(r,MO(u));}TE IN U Module::Action(CO R& r,U u){RE MO(u *= r);}TE IN U VirtualRSet::PW(U u,CO R& r){RE Action(r,MO(u));}TE IN U VirtualRSet::ScalarProduct(CO R& r,U u){RE Action(r,MO(u));} IN CE int Sqrt(CRI N)NE{if(N <= 1){RE 1;}int left = 0;int right = N;WH(left + 1 < right){int m =(left + right)/ 2;(m <=(N - 1)/ m?left:right)= m;}RE right;} #define SFINAE_FOR_SD_S enable_if_t>* TE CL IntervalSetSqrtDecomposition{PU:NON_COMM_N_MODULE m_M;int m_N;int m_N_sqrt;int m_N_d;int m_N_m;VE m_a;VE m_b;VE m_lazy_substitution;VE m_suspENed;IN IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,CRI N = 0);IN IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,CRI N,CRI N_sqrt);IN IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE a);IN IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE a,CRI N_sqrt);TE IN VO Initialise(Args&&... args);IN VO Set(CRI i,CO U& u);IN VO IntervalSet(CRI i_start,CRI i_final,CO U& u);IN U OP[](CRI i);IN U Get(CRI i);IN U IntervalProduct(CRI i_start,CRI i_final);TE IN int Search(CRI i_start,CO F& f);IN int Search(CRI i_start,CO U& u);IN VO IntervalSet_Body(CRI i_min,CRI i_ulim,CO U& u);IN U IntervalProduct_Body(CRI i_min,CRI i_ulim);TE int Search_Body(CRI i_start,CO F& f,U sum_temp);};TE IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,Args&&... args)-> IntervalSetSqrtDecomposition,NON_COMM_N_MODULE>; TE IN IntervalSetSqrtDecomposition::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,CRI N):IntervalSetSqrtDecomposition(MO(M),N,Sqrt(N)){}TE IN IntervalSetSqrtDecomposition::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,CRI N,CRI N_sqrt):m_M(MO(M)),m_N(N),m_N_sqrt(N_sqrt),m_N_d((m_N + m_N_sqrt - 1)/ m_N_sqrt),m_N_m(m_N_d * m_N_sqrt),m_a(m_N_m,m_M.One()),m_b(m_N_d,m_M.One()),m_lazy_substitution(m_N_d,m_M.One()),m_suspENed(m_N_d){ST_AS(! is_same_v && is_same_v>);}TE IN IntervalSetSqrtDecomposition::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE a):IntervalSetSqrtDecomposition(MO(M),MO(a),Sqrt(a.SZ())){}TE IN IntervalSetSqrtDecomposition::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE a,CRI N_sqrt):m_M(MO(M)),m_N(a.SZ()),m_N_sqrt(N_sqrt),m_N_d((m_N + m_N_sqrt - 1)/ m_N_sqrt),m_N_m(m_N_d * m_N_sqrt),m_a(MO(a)),m_b(m_N_d,m_M.One()),m_lazy_substitution(m_N_d,m_M.One()),m_suspENed(m_N_d){ST_AS(! is_same_v && is_same_v>);m_a.reSZ(m_N_m,m_M.One());int i_min = 0;int i_ulim = m_N_sqrt;for(int d = 0;d < m_N_d;d++){U& m_bd = m_b[d];for(int i = i_min;i < i_ulim;i++){m_bd = m_M.Product(MO(m_bd),m_a[i]);}i_min = i_ulim;i_ulim += m_N_sqrt;}}TE TE IN VO IntervalSetSqrtDecomposition::Initialise(Args&&... args){IntervalSetSqrtDecomposition temp{m_M,forward(args)...};m_N = temp.m_N;m_N_sqrt = temp.m_N_sqrt;m_N_d = temp.m_N_d;m_N_m = temp.m_N_m;m_a = MO(temp.m_a);m_b = MO(temp.m_b);m_lazy_substitution = VE(m_N_d,m_M.One());m_suspENed = VE(m_N_d,false);}TE IN VO IntervalSetSqrtDecomposition::Set(CRI i,CO U& u){IntervalSet(i,i,u);}TE IN VO IntervalSetSqrtDecomposition::IntervalSet(CRI i_start,CRI i_final,CO U& u){CO int i_min = max(i_start,0);CO int i_ulim = min(i_final + 1,m_N);CO int d_0 =(i_min + m_N_sqrt - 1)/ m_N_sqrt;CO int d_1 = max(d_0,i_ulim / m_N_sqrt);CO int d_0_N_sqrt = d_0 * m_N_sqrt;CO int d_1_N_sqrt = d_1 * m_N_sqrt;CO int i_0 = min(d_0_N_sqrt,i_ulim);CO int i_1 = max(i_0,d_1_N_sqrt);if(i_min < i_0){CO int d_0_minus = d_0 - 1;CO int d_0_N_sqrt_minus = d_0_N_sqrt - m_N_sqrt;U& m_bd = m_b[d_0_minus];VE::reference m_suspENed_d = m_suspENed[d_0_minus];if(m_suspENed_d){U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];IntervalSet_Body(d_0_N_sqrt_minus,i_min,m_lazy_substitution_d);IntervalSet_Body(i_min,i_0,u);IntervalSet_Body(i_0,d_0_N_sqrt,m_lazy_substitution_d);m_suspENed_d = false;m_bd = m_M.Product(m_M.PW(m_lazy_substitution_d,m_N_sqrt -(i_0 - i_min)),m_M.PW(u,i_0 - i_min));}else{IntervalSet_Body(i_min,i_0,u);m_bd = m_M.Product(m_M.Product(IntervalProduct_Body(d_0_N_sqrt_minus,i_min),m_M.PW(u,i_0 - i_min)),IntervalProduct_Body(i_0,d_0_N_sqrt));}}CO U PW = m_M.PW(u,m_N_sqrt);for(int d = d_0;d < d_1;d++){m_b[d]= PW;m_lazy_substitution[d]= u;m_suspENed[d]= true;}if(i_1 < i_ulim){CO int d_1_N_sqrt_plus = d_1_N_sqrt + m_N_sqrt;U& m_bd = m_b[d_1];VE::reference m_suspENed_d = m_suspENed[d_1];if(m_suspENed_d){U& m_lazy_substitution_d = m_lazy_substitution[d_1];IntervalSet_Body(d_1_N_sqrt,i_1,m_lazy_substitution_d);IntervalSet_Body(i_1,i_ulim,u);IntervalSet_Body(i_ulim,d_1_N_sqrt_plus,m_lazy_substitution_d);m_suspENed_d = false;m_bd = m_M.Product(m_M.Product(m_M.PW(m_lazy_substitution_d,i_1 - d_1_N_sqrt),m_M.PW(u,i_ulim - i_1)),m_M.PW(m_lazy_substitution_d,d_1_N_sqrt_plus - i_ulim));}else{IntervalSet_Body(i_1,i_ulim,u);m_bd = m_M.Product(m_M.Product(IntervalProduct_Body(d_1_N_sqrt,i_1),m_M.PW(u,i_ulim - i_1)),IntervalProduct_Body(i_ulim,d_1_N_sqrt_plus));}}RE;}TE IN VO IntervalSetSqrtDecomposition::IntervalSet_Body(CRI i_min,CRI i_ulim,CO U& u){for(int i = i_min;i < i_ulim;i++){m_a[i]= u;}RE;}TE IN U IntervalSetSqrtDecomposition::OP[](CRI i){AS(0 <= i && i < m_N);CO int d = i / m_N_sqrt;RE m_suspENed[d]?m_lazy_substitution[d]:m_a[i];}TE IN U IntervalSetSqrtDecomposition::Get(CRI i){RE OP[](i);}TE IN U IntervalSetSqrtDecomposition::IntervalProduct(CRI i_start,CRI i_final){CO int i_min = max(i_start,0);CO int i_ulim = min(i_final + 1,m_N);CO int d_0 =(i_min + m_N_sqrt - 1)/ m_N_sqrt;CO int d_1 = max(d_0,i_ulim / m_N_sqrt);CO int i_0 = min(d_0 * m_N_sqrt,i_ulim);CO int i_1 = max(i_0,d_1 * m_N_sqrt);U AN = m_M.One();if(i_min < i_0){CO int d_0_minus = d_0 - 1;AN = m_suspENed[d_0_minus]?m_M.PW(m_lazy_substitution[d_0_minus],i_0 - i_min):IntervalProduct_Body(i_min,i_0);}for(int d = d_0;d < d_1;d++){AN = m_M.Product(MO(AN),m_b[d]);}if(i_1 < i_ulim){AN = m_M.Product(MO(AN),m_suspENed[d_1]?m_M.PW(m_lazy_substitution[d_1],i_ulim - i_1):IntervalProduct_Body(i_1,i_ulim));}RE AN;}TE IN U IntervalSetSqrtDecomposition::IntervalProduct_Body(CRI i_min,CRI i_ulim){U AN = m_M.One();for(int i = i_min;i < i_ulim;i++){AN = m_M.Product(MO(AN),m_a[i]);}RE AN;}TE TE IN int IntervalSetSqrtDecomposition::Search(CRI i_start,CO F& f){RE Search_Body(i_start,f,m_M.One());}TE IN int IntervalSetSqrtDecomposition::Search(CRI i_start,CO U& u){RE Search(i_start,[&](CO U& product,CRI){RE !(u < product);});}TE TE int IntervalSetSqrtDecomposition::Search_Body(CRI i_start,CO F& f,U product_temp){CO int i_min = max(i_start,0);CO int d_0 =(i_min + m_N_sqrt - 1)/ m_N_sqrt;CO int i_0 = min(d_0 * m_N_sqrt,m_N);if(i_min < i_0){CO int d_0_minus = d_0 - 1;if(m_suspENed[d_0_minus]){CO U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];U product_next = m_M.Product(product_temp,m_lazy_substitution_d);if(f(product_next,i_min)){RE i_min;}int l = i_min,r = i_0;WH(l + 1 < r){int m =(l + r)/ 2;product_next = m_M.Product(product_temp,m_M.PW(m_lazy_substitution_d,m - i_min + 1));(f(product_next,m)?r:l)= m;}if(r < i_0){RE r;}product_temp = MO(product_next);}else{for(int i = i_min;i < i_0;i++){product_temp = m_M.Product(MO(product_temp),m_a[i]);if(f(product_temp,i)){RE i;}}}}int N_sqrt_d = m_N_sqrt * d_0;for(int d = d_0;d < m_N_d;d++,N_sqrt_d += m_N_sqrt){CO int j_rest = d + 1 < m_N_d?m_N_sqrt:m_N - N_sqrt_d;U product_next = m_M.Product(product_temp,m_suspENed[d]?m_M.PW(m_lazy_substitution[d],j_rest):m_b[d]);if(f(product_next,N_sqrt_d + j_rest - 1)){RE Search_Body(N_sqrt_d,f,product_temp);}product_temp = MO(product_next);}RE -1;} // AAA 常設でないライブラリは以上に挿入する。 #define INCLUDE_SUB #include __FILE__ #else // INCLUDE_LIBRARY #ifdef DEBUG #else // #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if CE( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FINISH_MAIN #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 ) #define ASSERT( A , MIN , MAX ) AS( ( MIN ) <= A && A <= ( MAX ) ) #define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX ) #define SOLVE_ONLY #define CERR( ... ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define CERR_A( A , N ) #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL #define CERR_ITR( A ) #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL #endif #ifdef REACTIVE #define ENDL endl #else #define ENDL "\n" #endif #ifdef USE_GETLINE #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); } #define GETLINE_SEPARATE( SEPARATOR , ... ) SOLVE_ONLY; string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) SOLVE_ONLY; GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET_LL( A ) cin >> A #define CIN( LL , ... ) SOLVE_ONLY; LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ ) #define SET_A( A , N ) SOLVE_ONLY; FOR( VARIABLE_FOR_SET_A , 0 , N ){ cin >> A[VARIABLE_FOR_SET_A]; } #define CIN_A( LL , A , N ) VE A( N ); SET_A( A , N ); #endif #include using namespace std; #define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) ) #define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define FINISH_MAIN REPEAT( test_case_num ){ if CE( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } } #define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now() #define CURRENT_TIME static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) CE LL BOUND = VALUE #define SET_A_ASSERT( A , N , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A] , MIN , MAX ); } #define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define CIN_A_ASSERT( A , N , MIN , MAX ) vector A( N ); SET_A_ASSERT( A , N , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- ) #define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .BE() , end_ ## ARRAY = ARRAY .EN() #define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ) #define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS #define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.BE() , EN_FOR_OUTPUT_ITR = A.EN(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; WH( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS #define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); RE #define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ ); auto answer = Answer( __VA_ARGS__ ); bool match = naive == answer; COUT( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Naive == " , naive , match ? "==" : "!=" , answer , "== Answer" ); if( !match ){ RE; } // 圧縮用 #define TE template #define TY typename #define US using #define ST static #define AS assert #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define LE length #define PW Power #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define VI virtual #define ST_AS static_assert #define reMO_CO remove_const #define is_COructible_v is_constructible_v #define rBE rbegin #define reSZ resize // 型のエイリアス #define decldecay_t(VAR)decay_t TE US ret_t = decltype(declval()(declval()...)); TE US inner_t = TY T::type; US uint = unsigned int; US ll = long long; US ull = unsigned long long; US ld = long double; US lld = __float128; TE US T2 = pair; TE US T3 = tuple; TE US T4 = tuple; US path = pair; // 入出力用 #define DF_OF_COUT_FOR_VE(V)TE IN basic_ostream& OP<<(basic_ostream& os,CO V& arg){auto BE = arg.BE(),EN = arg.EN();auto IT = BE;WH(IT != EN){(IT == BE?os:os << " ")<< *IT;IT++;}RE os;} TE IN basic_istream& VariadicCin(basic_istream& is){RE is;} TE IN basic_istream& VariadicCin(basic_istream& is,Arg& arg,ARGS&... args){RE VariadicCin(is >> arg,args...);} TE IN basic_istream& VariadicGetline(basic_istream& is,CO char& separator){RE is;} TE IN basic_istream& VariadicGetline(basic_istream& is,CO char& separator,Arg& arg,ARGS&... args){RE VariadicGetline(getline(is,arg,separator),separator,args...);} DF_OF_COUT_FOR_VE(VE); DF_OF_COUT_FOR_VE(LI); DF_OF_COUT_FOR_VE(set); DF_OF_COUT_FOR_VE(unordered_set); TE IN basic_ostream& OP<<(basic_ostream& os,CO pair& arg){RE os << arg.first << " " << arg.second;} TE IN basic_ostream& VariadicCout(basic_ostream& os,CO Arg& arg){RE os << arg;} TE IN basic_ostream& VariadicCout(basic_ostream& os,CO Arg1& arg1,CO Arg2& arg2,CO ARGS&... args){RE VariadicCout(os << arg1 << " ",arg2,args...);} // デバッグ用 #ifdef DEBUG #else ll GetRand( CRL Rand_min , CRL Rand_max ) { ll answer = time( NULL ); RE answer * rand() % ( Rand_max + 1 - Rand_min ) + Rand_min; } #endif // VVV 常設ライブラリは以下に挿入する。 // Map (1KB) // c:/Users/user/Documents/Programming/Mathematics/Function/Map/compress.txt CL is_ordered{PU:is_ordered()= delete;TE ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE ST CE CO bool value = is_same_v< decltype(Check(declval())),true_type >;}; TE US Map = conditional_t>,unordered_map,conditional_t,map,VO>>; // Algebra (4KB) // c:/Users/user/Documents/Programming/Mathematics/Algebra/compress.txt #define DC_OF_CPOINT(POINT)IN CO U& POINT()CO NE #define DC_OF_POINT(POINT)IN U& POINT()NE #define DF_OF_CPOINT(POINT)TE IN CO U& VirtualPointedSet::POINT()CO NE{RE Point();} #define DF_OF_POINT(POINT)TE IN U& VirtualPointedSet::POINT()NE{RE Point();} TE CL UnderlyingSet{PU:US type = U;};TE CL VirtualPointedSet:VI PU UnderlyingSet{PU:VI CO U& Point()CO NE = 0;VI U& Point()NE = 0;DC_OF_CPOINT(Unit);DC_OF_CPOINT(Zero);DC_OF_CPOINT(One);DC_OF_CPOINT(Infty);DC_OF_POINT(init);DC_OF_POINT(root);};TE CL PointedSet:VI PU VirtualPointedSet{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE CL VirtualNSet:VI PU UnderlyingSet{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE CL AbstractNSet:VI PU VirtualNSet{PU:F_U m_f_U;IN AbstractNSet(F_U f_U);IN U Transfer(CO U& u);};TE CL VirtualMagma:VI PU UnderlyingSet{PU:VI U Product(U u0,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE CL AdditiveMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL MultiplicativeMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL AbstractMagma:VI PU VirtualMagma{PU:M_U m_m_U;IN AbstractMagma(M_U m_U);IN U Product(U u0,CO U& u1);}; TE IN PointedSet::PointedSet(U b_U):m_b_U(MO(b_U)){}TE IN CO U& PointedSet::Point()CO NE{RE m_b_U;}TE IN U& PointedSet::Point()NE{RE m_b_U;}DF_OF_CPOINT(Unit);DF_OF_CPOINT(Zero);DF_OF_CPOINT(One);DF_OF_CPOINT(Infty);DF_OF_POINT(init);DF_OF_POINT(root);TE IN AbstractNSet::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v);}TE IN U AbstractNSet::Transfer(CO U& u){RE m_f_U(u);}TE IN U VirtualNSet::Inverse(CO U& u){RE Transfer(u);}TE IN AbstractMagma::AbstractMagma(M_U m_U):m_m_U(MO(m_U)){ST_AS(is_invocable_r_v);}TE IN U AdditiveMagma::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE IN U MultiplicativeMagma::Product(U u0,CO U& u1){RE MO(u0 *= u1);}TE IN U AbstractMagma::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE IN U VirtualMagma::Sum(U u0,CO U& u1){RE Product(MO(u0),u1);}TE CL VirtualMonoid:VI PU VirtualMagma,VI PU VirtualPointedSet{};TE CL AdditiveMonoid:VI PU VirtualMonoid,PU AdditiveMagma,PU PointedSet{};TE CL MultiplicativeMonoid:VI PU VirtualMonoid,PU MultiplicativeMagma,PU PointedSet{PU:IN MultiplicativeMonoid(U e_U);};TE