#ifndef INCLUDE_MODE #define INCLUDE_MODE /* #define SUBMIT_ONLY */ #define DEBUG_OUTPUT #endif #ifdef INCLUDE_MAIN VO Solve() { CIN( int , N ); CIN_A( int , 0 , N , A ); --A; CIN( int , Q ); Trop<>::SetZero( -1e5 ); using U = Matrix>; U E{ 4 , 4 }; vector M( 4 , E ); FOR( i , 0 , 4 ){ E[i][i] = 0; } FOR( i , 0 , 4 ){ FOR( j , 0 , 4 ){ FOR( k , j , 4 ){ M[i][j][k] = j <= i && i <= k ? 1 : 0; } } } auto UPower = [&]( const int& i , U a ){ return Power( move( a ) , i , E ); }; vector X_pre( N ); FOR( i , 0 , N ){ X_pre[i] = M[A[i]]; } IntervalSetMonoidSqrtDecomposition X{ AbstractModule( 0 , UPower , MultiplicativeMonoid( E ) ) , move( X_pre ) }; FOR( q , 0 , Q ){ CIN( int , type ); if( type == 1 ){ CIN( ll , x , y ); x--; y--; auto a = X.IntervalProduct( x , y ); COUT( a[0][3].Get() ); } else if( type == 2 ){ CIN( ll , x , y , n ); x--; y--; n--; X.IntervalSet( x , y , M[n] ); } } } REPEAT_MAIN(1); #else /* INCLUDE_MAIN */ #ifdef INCLUDE_SUB /* 圧縮時は中身だけ削除する。*/ IN VO Experiment() { } /* 圧縮時は中身だけ削除する。*/ IN VO SmallTest() { CERR( "全てのケースを確認しました。" ); } /* 圧縮時は中身だけ削除する。*/ IN VO RandomTest( const int& test_case_num ) { REPEAT( test_case_num ){ } CERR( "全てのケースを確認しました。" ); } #define INCLUDE_MAIN #include __FILE__ #else /* INCLUDE_SUB */ #ifdef INCLUDE_LIBRARY /* VVV 常設でないライブラリは以下に挿入する。*/ #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Mathematics/Algebra/Monoid/Semirng/MeetSemirng/Implement/a_Body.hpp" #else 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();} #endif #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Mathematics/LinearAlgebra/a_Body.hpp" #else #define MA Matrix TE CL MA{PU:int m_Y;int m_X;VE> m_M;IN MA(CRI Y = 0,CRI X = 0)NE;IN MA(CRI Y,CRI X,CO T& t)NE;TE IN MA(CRI Y,CRI X,Arg0&& t0,Arg1&& t1,Args&&... args)NE;IN MA(CO MA& mat)NE;IN MA(MA&& mat)NE;IN MA(CO VE>& mat)NE;IN MA(VE>&& mat)NE;IN MA& OP=(CO MA& mat)NE;IN MA& OP=(MA&& mat)NE;IN MA& OP=(VE> mat);IN MA& OP+=(CO MA& mat);IN MA& OP-=(CO MA& mat);IN MA& OP*=(CO T& scalar)NE;IN MA& OP*=(CO MA& mat);IN MA& OP/=(CO T& scalar);IN MA& OP%=(CO T& scalar);TE IN MA& OP^=(INT EX);IN bool OP==(CO MA& mat)CO NE;IN bool OP!=(CO MA& mat)CO NE;IN MA OP+(CO MA& mat)CO;IN MA OP-(CO MA& mat)CO;IN MA OP*(CO T& scalar)CO NE;IN MA OP*(CO MA& mat)CO;IN MA OP/(CO T& scalar)CO;IN MA OP%(CO T& scalar)CO;TE IN MA OP^(INT EX)CO;IN MA TP()CO NE;IN T Trace()CO NE;IN CRI GetCodomainDimension()CO NE;IN CRI GetDomainDimension()CO NE;IN CO VE>& GetEntry()CO NE;IN VE>& RefEntry()NE;IN CO VE& OP[](CRI y)CO;IN VE& OP[](CRI y);};TE CL Vector:PU MA{PU:IN Vector(CRI Y = 0)NE;TE IN Vector(Arg0&& t0,Arg1&& t1,Args&&... args)NE;IN Vector(CO MA& vec)NE;IN Vector(MA&& vec)NE;IN Vector(CO VE& vec)NE;IN Vector(VE&& vec)NE;IN Vector& OP=(CO MA& vec)NE;IN Vector& OP=(MA&& vec)NE;IN Vector& OP=(CO VE& vec);IN CO T& OP[](CRI y)CO;IN T& OP[](CRI y);IN CRI SZ()CO NE;}; TE IN MA::MA(CRI Y,CRI X)NE:m_Y(Y),m_X(X),m_M(Y,VE(X)){}TE IN Vector::Vector(CRI Y)NE:MA(Y,1){}TE IN MA::MA(CRI Y,CRI X,CO T& t)NE:MA(Y,X){CO int minXY = min(X,Y);for(int y = 0;y < minXY;y++){m_M[y][y]= t;};}TE TE IN MA::MA(CRI Y,CRI X,Arg0&& t0,Arg1&& t1,Args&&... args)NE:MA(Y,X){VE temp ={T(forward(t0)),T(forward(t1)),T(forward(args))...};AS(int(temp.SZ())== X * Y);int i = 0;for(int y = 0;y < Y;y++){for(int x = 0;x < X;x++){m_M[y][x]= MO(temp[i++]);}}}TE TE IN Vector::Vector(Arg0&& t0,Arg1&& t1,Args&&... args)NE:MA(2 + sizeof...(args),1,forward(t0),forward(t1),forward(args)...){}TE IN MA::MA(CO MA& mat)NE:m_Y(),m_X(),m_M(){*TH = mat.m_M;}TE IN Vector::Vector(CO MA& vec)NE:MA(vec){}TE IN MA::MA(MA&& mat)NE:m_Y(),m_X(),m_M(){*TH = MO(mat.m_M);}TE IN Vector::Vector(MA&& vec)NE:MA(MO(vec)){}TE IN MA::MA(CO VE>& mat)NE:m_Y(),m_X(),m_M(){*TH = mat;}TE IN Vector::Vector(CO VE& vec)NE:MA(){*TH = vec;}TE IN MA::MA(VE>&& mat)NE:m_Y(),m_X(),m_M(){*TH = MO(mat);}TE IN Vector::Vector(VE&& vec)NE:MA(){*TH = MO(vec);}TE IN MA& MA::OP=(CO MA& mat)NE{RE *TH = mat.m_M;}TE IN Vector& Vector::OP=(CO MA& vec)NE{MA& mat = *TH;mat = vec;AS(TH->m_X == 1);RE *TH;}TE IN MA& MA::OP=(MA&& mat)NE{RE *TH = MO(mat.m_M);}TE IN Vector& Vector::OP=(MA&& vec)NE{MA& mat = *TH;mat = MO(vec);AS(TH->m_X == 1);RE *TH;}TE IN MA& MA::OP=(VE> mat){m_M = MO(mat);m_X =(m_Y = m_M.SZ())> 0?int(m_M[0].SZ()):0;for(int y = 1;y < m_Y;y++){AS(int(m_M[y].SZ())== m_X);}RE *TH;}TE IN Vector& Vector::OP=(CO VE& vec){TH->m_M.resize(TH->m_Y = vec.SZ(),VE(TH->m_X = 1));for(int y = 0;y < TH->m_Y;y++){TH->m_M[y][0]= vec[y];}RE *TH;}TE IN MA& MA::OP+=(CO MA& mat){AS(m_X == mat.m_X && m_Y == mat.m_Y);for(int y = 0;y < m_Y;y++){auto& m_M_y = m_M[y];auto& mat_y = mat.m_M[y];for(int x = 0;x < m_X;x++){m_M_y[x]+= mat_y[x];}}RE *TH;}TE IN MA& MA::OP-=(CO MA& mat){AS(m_X == mat.m_X && m_Y == mat.m_Y);for(int y = 0;y < m_Y;y++){auto& m_M_y = m_M[y];auto& mat_y = mat.m_M[y];for(int x = 0;x < m_X;x++){m_M_y[x]-= mat_y[x];}}RE *TH;}TE IN MA& MA::OP*=(CO T& scalar)NE{for(int y = 0;y < m_Y;y++){auto& m_M_y = m_M[y];for(int x = 0;x < m_X;x++){m_M_y[x]*= scalar;}}RE *TH;}TE IN MA& MA::OP*=(CO MA& mat){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(int y = 0;y < m_Y;y++){auto& m_M_y = m_M[y];for(int x = 0;x < m_X;x++){m_M_y[x]%= scalar;}}RE *TH;}TE TE IN MA& MA::OP^=(INT EX){AS(m_X == m_Y && EX >= 0);MA pw{m_X,m_Y,1};WH(EX > 0){(EX& 1)== 1?pw *= *TH:pw;*TH *= *TH;EX >>= 1;}RE *TH = MO(pw);}TE IN bool MA::OP==(CO MA& mat)CO NE{if(m_X != mat.m_X || m_Y != mat.m_Y){RE false;}for(int y = 0;y < m_Y;y++){auto& m_M_y = m_M[y];auto& mat_y = mat[y];for(int x = 0;x < m_X;x++){if(m_M_y[x]!= mat_y[x]){RE false;}}}RE true;}TE IN bool MA::OP!=(CO MA& mat)CO NE{RE !(*TH == mat);}TE IN MA MA::OP+(CO MA& mat)CO{RE MO(MA(*TH)+= mat);}TE IN MA MA::OP-(CO MA& mat)CO{RE MO(MA(*TH)-= mat);}TE IN MA MA::OP*(CO T& scalar)CO NE{RE MO(MA(*TH)*= scalar);}TE IN MA MA::OP*(CO MA& mat)CO{AS(m_X == mat.m_Y);MA prod{m_Y,mat.m_X};for(int y = 0;y < m_Y;y++){auto& m_M_y = m_M[y];auto& prod_y = prod.m_M[y];for(int x = 0;x < m_X;x++){auto& m_M_yx = m_M_y[x];auto& mat_x = mat.m_M[x];for(int z = 0;z < mat.m_X;z++){prod_y[z]+= m_M_yx * mat_x[z];}}}RE prod;}TE IN MA MA::OP/(CO T& scalar)CO{RE MO(MA(*TH)/= scalar);}TE IN MA MA::OP%(CO T& scalar)CO{RE MO(MA(*TH)%= scalar);}TE TE IN MA MA::OP^(INT EX)CO{RE MO(MA(*TH)%= MO(EX));}TE IN MA MA::TP()CO NE{MA M_t{m_Y,m_X};for(int x = 0;x < m_X;x++){auto& M_t_x = M_t.m_M[x];for(int y = 0;y < m_Y;y++){M_t_x[y]= m_M[y][x];}}RE M_t;}TE IN T MA::Trace()CO NE{CE CO int minXY = min(m_X,m_Y);T AN{};for(int y = 0;y < minXY;y++){AN += m_M[y][y];}RE AN;}TE IN CRI MA::GetCodomainDimension()CO NE{RE m_Y;}TE IN CRI MA::GetDomainDimension()CO NE{RE m_X;}TE IN CO VE>& MA::GetEntry()CO NE{RE m_M;}TE IN CRI Vector::SZ()CO NE{RE TH->m_Y;}TE IN CO VE& MA::OP[](CRI y)CO{AS(0 <= y && y < m_Y);RE m_M[y];}TE IN CO T& Vector::OP[](CRI y)CO{AS(0 <= y && y < TH->m_Y);RE TH->m_M[y][0];}TE IN VE& MA::OP[](CRI y){AS(0 <= y && y < m_Y);RE m_M[y];}TE IN T& Vector::OP[](CRI y){AS(0 <= y && y < TH->m_Y);RE TH->m_M[y][0];}TE IN MA OP*(CO T& scalar,CO MA& mat)NE{RE mat * scalar;}TE IN MA Power(MA mat,INT EX){RE MO(mat ^= MO(EX));}TE IN MA Act(MA mat,INT EX,MA v){AS(EX >= 0);WH(EX > 0){(EX & 1)== 0?v:v = mat * v;mat *= mat;EX >>= 1;}RE MO(v);}TE IN OS& OP<<(OS& os,CO Vector& v){auto& Y = v.SZ();for(int y = 0;y < Y;y++){(y == 0?os:os << ' ')<< v[y];}RE os;} #endif #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Mathematics/SetTheory/DirectProduct/AffineSpace/SqrtDecomposition/Monoid/IntervalSet/a_Body.hpp" #else CL SqrtDecompositionCoordinate{PU:int m_N;int m_N_sqrt;int m_N_d;int m_N_m;IN SqrtDecompositionCoordinate(CRI N = 0);IN SqrtDecompositionCoordinate(CRI N,CRI N_sqrt);IN CRI size()CO NE;IN CRI BucketSize()CO NE;IN CRI BucketCount()CO NE;}; IN SqrtDecompositionCoordinate::SqrtDecompositionCoordinate(CRI N):SqrtDecompositionCoordinate(N,RoundUpSqrt(N)){};IN SqrtDecompositionCoordinate::SqrtDecompositionCoordinate(CRI N,CRI N_sqrt):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){}IN CRI SqrtDecompositionCoordinate::size()CO NE{RE m_N;}IN CRI SqrtDecompositionCoordinate::BucketSize()CO NE{RE m_N_sqrt;}IN CRI SqrtDecompositionCoordinate::BucketCount()CO NE{RE m_N_d;} #define SFINAE_FOR_SD_S enable_if_t>* TE CL IntervalSetMonoidSqrtDecomposition:PU SqrtDecompositionCoordinate{PU:NON_COMM_N_MODULE m_M;VE m_a;VE m_b;VE m_lazy_substitution;VE m_suspended;TE IN IntervalSetMonoidSqrtDecomposition(NON_COMM_N_MODULE M,CRI N = 1,CO Args&... args);TE IntervalSetMonoidSqrtDecomposition(NON_COMM_N_MODULE M,VE a,CO Args&... args);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,CO bool& reversed = false);IN int Search(CRI i_start,CO U& u,CO bool& reversed = false);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 int SearchReverse_Body(CRI i_final,CO F& f,U sum_temp);};TE IntervalSetMonoidSqrtDecomposition(NON_COMM_N_MODULE M,Args&&... args)-> IntervalSetMonoidSqrtDecomposition,NON_COMM_N_MODULE>; TE TE IN IntervalSetMonoidSqrtDecomposition::IntervalSetMonoidSqrtDecomposition(NON_COMM_N_MODULE M,CRI N,CO Args&... args):SqrtDecompositionCoordinate(N,args...),m_M(MO(M)),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_suspended(m_N_d){ST_AS(! is_same_v && is_same_v>);}TE TE IntervalSetMonoidSqrtDecomposition::IntervalSetMonoidSqrtDecomposition(NON_COMM_N_MODULE M,VE a,CO Args&... args):SqrtDecompositionCoordinate(a.SZ(),args...),m_M(MO(M)),m_a(MO(a)),m_b(m_N_d,m_M.One()),m_lazy_substitution(m_N_d,m_M.One()),m_suspended(m_N_d){ST_AS(! is_same_v && is_same_v>);m_a.resize(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 IntervalSetMonoidSqrtDecomposition::Initialise(Args&&... args){IntervalSetMonoidSqrtDecomposition temp{m_M,forward(args)...};SqrtDecompositionCoordinate::OP=(temp);m_a = MO(temp.m_a);m_b = MO(temp.m_b);m_lazy_substitution = MO(temp.m_lazy_substitution);m_suspended = MO(temp.m_suspended);}TE IN VO IntervalSetMonoidSqrtDecomposition::Set(CRI i,CO U& u){IntervalSet(i,i,u);}TE IN VO IntervalSetMonoidSqrtDecomposition::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_suspended_d = m_suspended[d_0_minus];if(m_suspended_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_suspended_d = false;m_bd = m_M.Product(m_M.Product(m_M.Power(m_lazy_substitution_d,i_min - d_0_N_sqrt_minus),m_M.Power(u,i_0 - i_min)),m_M.Power(m_lazy_substitution_d,d_0_N_sqrt - i_0));}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.Power(u,i_0 - i_min)),IntervalProduct_Body(i_0,d_0_N_sqrt));}}CO U pw = m_M.Power(u,m_N_sqrt);for(int d = d_0;d < d_1;d++){m_b[d]= pw;m_lazy_substitution[d]= u;m_suspended[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_suspended_d = m_suspended[d_1];if(m_suspended_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_suspended_d = false;m_bd = m_M.Product(m_M.Product(m_M.Power(m_lazy_substitution_d,i_1 - d_1_N_sqrt),m_M.Power(u,i_ulim - i_1)),m_M.Power(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.Power(u,i_ulim - i_1)),IntervalProduct_Body(i_ulim,d_1_N_sqrt_plus));}}RE;}TE IN VO IntervalSetMonoidSqrtDecomposition::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 IntervalSetMonoidSqrtDecomposition::OP[](CRI i){AS(0 <= i && i < m_N);CO int d = i / m_N_sqrt;RE m_suspended[d]?m_lazy_substitution[d]:m_a[i];}TE IN U IntervalSetMonoidSqrtDecomposition::Get(CRI i){RE OP[](i);}TE IN U IntervalSetMonoidSqrtDecomposition::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_suspended[d_0_minus]?m_M.Power(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_suspended[d_1]?m_M.Power(m_lazy_substitution[d_1],i_ulim - i_1):IntervalProduct_Body(i_1,i_ulim));}RE AN;}TE IN U IntervalSetMonoidSqrtDecomposition::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 IntervalSetMonoidSqrtDecomposition::Search(CRI i_start,CO F& f,CO bool& reversed){RE reversed?SearchReverse_Body(i_start,f,m_M.One()):Search_Body(i_start,f,m_M.One());}TE IN int IntervalSetMonoidSqrtDecomposition::Search(CRI i_start,CO U& u,CO bool& reversed){RE Search(i_start,[&](CO U& product,CRI){RE !(product < u);},reversed);}TE TE int IntervalSetMonoidSqrtDecomposition::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;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_suspended[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)>> 1;product_next = m_M.Product(product_temp,m_M.Power(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_suspended[d]?m_M.Power(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,MO(product_temp));}product_temp = MO(product_next);}RE -1;}TE TE int IntervalSetMonoidSqrtDecomposition::SearchReverse_Body(CRI i_final,CO F& f,U product_temp){CO int i_max = min(i_final,m_N - 1);CO int d_1 = i_max / m_N_sqrt;CO int i_1 = max(d_1 * m_N_sqrt,0);if(m_suspended[d_1]){CO U& m_lazy_substitution_d = m_lazy_substitution[d_1];U product_next = m_M.Product(product_temp,m_lazy_substitution_d);if(f(product_next,i_max)){RE i_max;}int l = i_1,r = i_max;WH(l + 1 < r){int m =(l + r)>> 1;product_next = m_M.Product(m_M.Power(m_lazy_substitution_d,i_max - m + 1),product_temp);(f(product_next,m)?l:r)= m;}if(i_1 < l){RE l;}product_temp = MO(product_next);}else{for(int i = i_max;i >= i_1;i--){product_temp = m_M.Product(m_a[i],product_temp);if(f(product_temp,i)){RE i;}}}for(int d = d_1 - 1;d >= 0;d--){U product_next = m_M.Product(m_suspended[d]?m_M.Power(m_lazy_substitution[d],m_N_sqrt):m_b[d],product_temp);if(f(product_next,d * m_N_sqrt)){RE Search_Body((d + 1)* m_N_sqrt - 1,f,MO(product_temp));}product_temp = MO(product_next);}RE -1;} #endif /* AAA 常設でないライブラリは以上に挿入する。*/ #define INCLUDE_SUB #include __FILE__ #else /* INCLUDE_LIBRARY */ #ifdef DEBUG #define _GLIBCXX_DEBUG #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 ) #define ASSERT( A , MIN , MAX ) AS( ( MIN ) <= A && A <= ( MAX ) ) #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , test_case_num_bound , BOUND ); int test_case_num = 1; if CE( test_case_num_bound > 1 ){ FINISH_MAIN #ifdef USE_GETLINE #define SET_SEPARATE( SEPARATOR , ... ) VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define SET( ... ) SET_SEPARATE( '\n' , __VA_ARGS__ ) #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; SET_SEPARATE( SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #define FINISH_MAIN GETLINE( test_case_num_str ); test_case_num = stoi( test_case_num_str ); ASSERT( test_case_num , 1 , test_case_num_bound ); } REPEAT( test_case_num ){ Solve(); } } #else #define SET( ... ) VariadicCin( cin , __VA_ARGS__ ) #define CIN( LL , ... ) LL __VA_ARGS__; SET( __VA_ARGS__ ) #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); } #define CIN_A( LL , I , N , ... ) VE __VA_ARGS__; SET_A( I , N , __VA_ARGS__ ) #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) VE VAR( N0 + I0 , VE( N1 + I1 ) ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); } #define FINISH_MAIN SET_ASSERT( test_case_num , 1 , test_case_num_bound ); } REPEAT( test_case_num ){ Solve(); } } #endif #define SET_ASSERT( A , MIN , MAX ) SET( A ); ASSERT( A , MIN , MAX ) #define SOLVE_ONLY #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ ) #define CERR( ... ) #define CERRNS( ... ) #define COUT_A( I , N , A ) CoutArray( cout , I , N , A ) << ENDL #define CERR_A( I , N , A ) #define WHAT( ... ) #define TLE( CONDITION ) if( !( CONDITION ) ){ cerr << "TLE" << endl; ll TLE_VAR = 1; while( TLE_VAR % 2 != 0 ){ ( TLE_VAR += 2 ) %= int( 1e9 ); } cerr << TLE_VAR << endl; } #define MLE( CONDITION ) if( !( CONDITION ) ){ cerr << "MLE" << endl; vector> MLE_VAR{}; REPEAT( 1e6 ){ MLE_VAR.push_back( vector( 1e6 ) ); } cerr << MLE_VAR << endl; } #define OLE( CONDITION ) if( !( CONDITION ) ){ cerr << "OLE" << endl; REPEAT( 1e8 ){ COUT( "OLE" ); } } #endif #ifdef REACTIVE #ifndef DEBUG #define LOCAL( ... ) #define RSET( A , ... ) SET( A ) #endif #define RCIN( LL , A , ... ) LL A; RSET( A , __VA_ARGS__ ) #define ENDL endl #else #define ENDL "\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 START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now(); double loop_average_time = 0.0 , loop_start_time = loop_average_time , current_time = loop_start_time; int loop_count = current_time; assert( loop_count == 0 ) #define CURRENT_TIME ( current_time = static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME , loop_count == 0 ? loop_start_time = current_time : loop_average_time = ( current_time - loop_start_time ) / loop_count , ++loop_count , current_time < TL_MS - loop_average_time * 2 - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) CE LL BOUND = VALUE #define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); } #define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } } #define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX ) #define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) #define PR1( A1 , ... ) A1 #define PR2( A1 , A2 , ... ) A2 #define PR3( A1 , A2 , A3 , ... ) A3 #define FOR_( VAR , INITIAL , FINAL , UPPER , COMP , INCR ) for( decldecay_t( UPPER ) VAR = INITIAL ; VAR COMP ( FINAL ) ; VAR INCR ) #define FOR( VAR , INITIAL , ... ) FOR_( VAR , INITIAL , PR1( __VA_ARGS__ ) , PR1( __VA_ARGS__ ) , < , PR3( __VA_ARGS__ , += PR2( __VA_ARGS__ , ? ) , ++ ) ) #define FOREQ( VAR , INITIAL , ... ) FOR_( VAR , INITIAL , PR1( __VA_ARGS__ ) , PR1( __VA_ARGS__ ) , <= , PR3( __VA_ARGS__ , += PR2( __VA_ARGS__ , ? ) , ++ ) ) #define FOREQINV( VAR , INITIAL , ... ) FOR_( VAR , INITIAL , PR1( __VA_ARGS__ ) , INITIAL , + 1 > , PR3( __VA_ARGS__ , -= PR2( __VA_ARGS__ , ? ) , -- ) ) #define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN() #define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ); cerr << fixed << setprecision( DECIMAL_DIGITS ) #define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); RE #define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ , false ); auto answer = Answer( __VA_ARGS__ , false ); bool match = naive == answer; CERR( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Naive ==" , naive , match ? "==" : "!=" , answer , "== Answer" ); if( !match ){ CERR( "出力の不一致が検出されました。" ); RE; } #define CHECK( ... ) auto answer = Answer( __VA_ARGS__ , false ); CERR( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Answer == " , answer ) /* 圧縮用 */ #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 MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define VI virtual #define IS basic_istream #define OS basic_ostream #define ST_AS static_assert #define reMO_CO remove_const #define is_COructible_v is_constructible_v #define rBE rbegin /* 型のエイリアス */ #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; /* VVV 常設ライブラリは以下に挿入する。*/ #ifdef DEBUG #include "C:/Users/user/Documents/Programming/Contest/Template/Local/a_Body.hpp" US MP = DMod; #else /* BinarySearch (2KB)*/ CE bool reactive = #ifdef REACTIVE true; #else false; #endif /* Random (1KB)*/ ll GetRand(CRL Rand_min,CRL Rand_max){AS(Rand_min <= Rand_max);ll AN = time(NULL);RE AN * rand()%(Rand_max + 1 - Rand_min)+ Rand_min;} /* Set (2KB)*/ #define DC_OF_HASH(...)struct hash<__VA_ARGS__>{IN size_t OP()(CO __VA_ARGS__& n)CO;}; 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 Set = conditional_t>,unordered_set,conditional_t,set,VO>>; #define DF_OF_POP_FOR_SET(SET)TE IN T pop_max(SET& S){AS(!S.empty());auto IT = --S.EN();T AN = *IT;S.erase(IT);RE AN;}TE IN T pop_min(SET& S){AS(!S.empty());auto IT = S.BE();T AN = *IT;S.erase(IT);RE AN;}TE IN SET& OP<<=(SET& S,T t){S.insert(MO(t));RE S;}TE IN SET& OP<<=(SET& S,U&& u){S.insert(T{forward(u)});RE S;}TE IN SET& OP>>=(SET& S,CO T& t){auto IT = S.find(t);if(IT != S.EN()){S.erase(IT);}RE S;}TE IN SET& OP>>=(SET& S,CO U& u){RE S >>= T{u};}TE IN CO T& Get(CO SET& S,int i){auto BE = S.BE(),EN = S.EN();auto& IT = i < 0?(++i,--EN):BE;WH(i > 0 && IT != EN){--i;++IT;}WH(i < 0 && IT != BE){++i;--IT;}AS(i == 0);RE *IT;} #define DF_OF_UNION_FOR_SET(SET)TE IN SET& OP|=(SET& S0,SET S1){S0.merge(MO(S1));RE S0;}TE IN SET OP|(SET S0,SET S1){RE MO(S0.SZ()< S1.SZ()?S1 |= MO(S0):S0 |= MO(S1));} TE IN TY SET::const_iterator MaximumLeq(CO SET& S,CO T& t){auto IT = S.upper_bound(t);RE IT == S.BE()?S.EN():--IT;}TE IN TY SET::const_iterator MaximumLt(CO SET& S,CO T& t){auto IT = S.lower_bound(t);RE IT == S.BE()?S.EN():--IT;}TE IN TY SET::const_iterator MinimumGeq(CO SET& S,CO T& t){RE S.lower_bound(t);}TE IN TY SET::const_iterator MinimumGt(CO SET& S,CO T& t){RE S.upper_bound(t);}TE IN VO EraseBack(SET& S,ITERATOR& IT){IT = S.erase(IT);}TE IN VO EraseFront(SET& S,ITERATOR& IT){IT = S.erase(IT);IT == S.BE()?IT = S.EN():--IT;}TE TY SET,TY T,TY...Args> IN bool In(CO T& t,CO SET& S){RE S.count(t)> 0;}DF_OF_POP_FOR_SET(set);DF_OF_POP_FOR_SET(unordered_set);DF_OF_POP_FOR_SET(multiset);DF_OF_POP_FOR_SET(unordered_multiset);DF_OF_UNION_FOR_SET(set);DF_OF_UNION_FOR_SET(unordered_set);DF_OF_UNION_FOR_SET(multiset);DF_OF_UNION_FOR_SET(unordered_multiset);DF_OF_UNION_FOR_SET(VE);DF_OF_UNION_FOR_SET(LI