#1049358 (C++17(gcc12)) No.2697 Range LIS Query

提出ソース
結果

問題	No.2697 Range LIS Query
ユーザー	👑 p-adic
提出日時	2025-03-05 08:14:30
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	29,823 bytes
コンパイル時間	13,468 ms
コンパイル使用メモリ	300,872 KB
実行使用メモリ	30,052 KB
最終ジャッジ日時	2025-03-05 08:15:14
合計ジャッジ時間	42,611 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 6 TLE * 1 -- * 8
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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<U> 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<U> 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 <TY U> CL Trop;TE <TY U>CL ZeroForTrop{PU:ZeroForTrop()= delete;ST U g_zero;};TE <TY U = ll>CL Trop{PU:U m_n;IN Trop(CO U& n = ZeroForTrop<U>::g_zero);IN Trop<U>& OP+=(CO Trop<U>& n);IN Trop<U>& OP*=(CO Trop<U>& n);IN Trop<U> OP+(CO Trop<U>& n)CO;IN Trop<U> OP*(CO Trop<U>& n)CO;IN VO Set(CO U& n)NE;IN CO U& Get()CO NE;ST IN VO SetZero(CO U& zero)NE;;};
TE <TY U> U ZeroForTrop<U>::g_zero{};TE <TY U> IN Trop<U>::Trop(CO U& n):m_n(n){}TE <TY U> IN Trop<U>& Trop<U>::OP+=(CO Trop<U>& n){n.m_n == ZeroForTrop<U>::g_zero?m_n:m_n =(m_n == ZeroForTrop<U>::g_zero?n.m_n:max(m_n,n.m_n));RE *TH;}TE <TY U> IN Trop<U>& Trop<U>::OP*=(CO Trop<U>& n){m_n == ZeroForTrop<U>::g_zero?m_n:m_n =(n.m_n == ZeroForTrop<U>::g_zero?ZeroForTrop<U>::g_zero:m_n + n.m_n);RE *TH;}TE <TY U> IN Trop<U> Trop<U>::OP+(CO Trop<U>& n)CO{RE MO(Trop<U>(*TH)+= n);}TE <TY U> IN Trop<U> Trop<U>::OP*(CO Trop<U>& n)CO{RE MO(Trop<U>(*TH)*= n);}TE <TY U> IN VO Trop<U>::Set(CO U& n)NE{m_n = n;}TE <TY U> IN CO U& Trop<U>::Get()CO NE{RE m_n;}TE <TY U> IN VO Trop<U>::SetZero(CO U& zero)NE{ZeroForTrop<U>::g_zero = zero;};TE <CL Traits,TY U> IN basic_istream<char,Traits>& OP>>(basic_ostream<char,Traits>& is,CO Trop<U>& n)NE{U temp;is >> temp;n.Set(temp);RE is;}TE <CL Traits,TY U> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Trop<U>& n)NE{RE os << n.Get();}

#define MA Matrix

#define SFINAE_FOR_MA(DEFAULT) TY Arg,enable_if_t<is_constructible<T,Arg>::value>* DEFAULT

TE <uint Y,uint X,TY T>CL MA{PU:T m_M[Y][X];IN MA()NE;IN MA(CO T& t)NE;IN MA(CRI t)NE;TE <TY Arg0,TY Arg1,TY... Args> IN MA(Arg0&& t0,Arg1&& t1,Args&&... args)NE;IN MA(CO MA<Y,X,T>& mat)NE;IN MA(MA<Y,X,T>&& mat)NE;TE <TY... Args> IN MA(CO T (&mat)[Y][X])NE;TE <TY... Args> IN MA(T (&&mat)[Y][X])NE;IN MA<Y,X,T>& OP=(CO MA<Y,X,T>& mat)NE;IN MA<Y,X,T>& OP=(MA<Y,X,T>&& mat)NE;IN MA<Y,X,T>& OP=(CO T (&mat)[Y][X])NE;IN MA<Y,X,T>& OP=(T (&&mat)[Y][X])NE;IN MA<Y,X,T>& OP+=(CO MA<Y,X,T>& mat)NE;IN MA<Y,X,T>& OP-=(CO MA<Y,X,T>& mat)NE;IN MA<Y,X,T>& OP*=(CO T& scalar)NE;IN MA<Y,X,T>& OP*=(CO MA<X,X,T>& mat)NE;IN MA<Y,X,T>& OP/=(CO T& scalar);IN MA<Y,X,T>& OP%=(CO T& scalar);IN bool OP==(CO MA<Y,X,T>& mat) CO NE;TE <uint Z> IN MA<Y,Z,T> OP*(CO MA<X,Z,T>& mat) CO NE;IN MA<X,Y,T> 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<Y,X,T>& Zero()NE;ST IN CO MA<Y,X,T>& One()NE;ST IN VO SetArray(T (&M)[Y][X],T (&&array)[Y * X])NE;};

TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA()NE:m_M(){}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::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 <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CRI t)NE:MA(T(t)){}TE <uint Y,uint X,TY T> TE <TY Arg0,TY Arg1,TY... Args> IN MA<Y,X,T>::MA(Arg0&& t0,Arg1&& t1,Args&&... args)NE:m_M(){T array[Y * X] ={T(forward<Arg0>(t0)),T(forward<Arg1>(t1)),T(forward<Args>(args))...};SetArray(m_M,MO(array));}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO MA<Y,X,T>& mat)NE:m_M(){OP=(mat.m_M);}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(MA<Y,X,T>&& mat)NE:m_M(){swap(m_M,mat.m_M);}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO T (&mat)[Y][X])NE:m_M(){OP=(mat);}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(T (&&mat)[Y][X])NE:m_M(){swap(m_M,mat);}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP=(CO MA<Y,X,T>& mat)NE{RE OP=(mat.m_M);}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP=(MA<Y,X,T>&& mat)NE{RE OP=(MO(mat.m_M));}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::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 <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP=(T (&&mat)[Y][X])NE{swap(m_M,mat);RE *TH;}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP+=(CO MA<Y,X,T>& 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 <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP-=(CO MA<Y,X,T>& 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 <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::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 <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP*=(CO MA<X,X,T>& mat)NE{RE OP=(MO(*TH * mat));}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP/=(CO T& scalar){RE OP*=(T(1) / scalar);}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::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 <uint Y,uint X,TY T> TE <uint Z> IN MA<Y,Z,T> MA<Y,X,T>::OP*(CO MA<X,Z,T>& mat) CO NE{MA<Y,Z,T> 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 <uint Y,uint X,TY T> IN bool MA<Y,X,T>::OP==(CO MA<Y,X,T>& 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 <uint Y,uint X,TY T> IN MA<X,Y,T> MA<Y,X,T>::Transpose() CO NE{MA<X,Y,T> 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 <uint Y,uint X,TY T> IN T MA<Y,X,T>::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 <uint Y,uint X,TY T> IN CO T(&MA<Y,X,T>::OP[](CRUI y)CO)[X]{AS(y < Y);RE m_M[y];}TE <uint Y,uint X,TY T> IN T(&MA<Y,X,T>::OP[](CRUI y))[X]{AS(y < Y);RE m_M[y];}TE <uint Y,uint X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Zero()NE{ST CO MA<Y,X,T> zero{};RE zero;}TE <uint Y,uint X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::One()NE{ST CO MA<Y,X,T> one{1};RE one;}TE <uint Y,uint X,TY T> IN VO MA<Y,X,T>::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 <uint Y,uint X,TY T> IN MA<Y,X,T> OP!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2)NE{RE !(mat1 == mat2);}TE <uint Y,uint X,TY T> IN MA<Y,X,T> OP+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2)NE{RE MO(MA<Y,X,T>(mat1) += mat2);}TE <uint Y,uint X,TY T> IN MA<Y,X,T> OP-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2)NE{RE MO(MA<Y,X,T>(mat1) -= mat2);}TE <uint Y,uint X,TY T> IN MA<Y,X,T> OP*(CO MA<Y,X,T>& mat,CO T& scalar)NE{RE MO(MA<Y,X,T>(mat) *= scalar);}TE <uint Y,uint X,TY T> IN MA<Y,X,T> OP*(CO T& scalar,CO MA<Y,X,T>& mat)NE{RE MO(MA<Y,X,T>(mat) *= scalar);}TE <uint Y,uint X,TY T> IN MA<Y,X,T> OP/(CO MA<Y,X,T>& mat,CO T& scalar){RE MO(MA<Y,X,T>(mat) /= scalar);}TE <uint Y,uint X,TY T> IN MA<Y,X,T> OP%(CO MA<Y,X,T>& mat,CO T& scalar){RE MO(MA<Y,X,T>(mat) %= scalar);}

TE <TY R,TY U>CL VirtualRSet:VI PU UnderlyingSet<U>{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 <TY U,TY MAGMA>CL RegularRSet:VI PU VirtualRSet<U,U>,PU MAGMA{PU:IN RegularRSet(MAGMA magma);IN U Action(CO U& r,U u);};TE <TY MAGMA> RegularRSet(MAGMA magma)-> RegularRSet<inner_t<MAGMA>,MAGMA>;TE <TY R,TY U,TY O_U>CL AbstractRSet:VI PU VirtualRSet<R,U>{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 <TY R,TY U,TY O_U,TY GROUP>CL AbstractModule:PU AbstractRSet<R,U,O_U>,PU GROUP{PU:IN AbstractModule(CO R& dummy,O_U o_U,GROUP M);};TE <TY R,TY O_U,TY GROUP> AbstractModule(CO R& dummy,O_U o_U,GROUP M)-> AbstractModule<R,inner_t<GROUP>,O_U,GROUP>;TE <TY R,TY U>CL Module:VI PU VirtualRSet<R,U>,PU AdditiveGroup<U>{PU:IN U Action(CO R& r,U u);};
TE <TY R,TY MAGMA> IN RegularRSet<R,MAGMA>::RegularRSet(MAGMA magma):MAGMA(MO(magma)){}TE <TY R,TY U,TY O_U> IN AbstractRSet<R,U,O_U>::AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U):m_o_U(MO(o_U)){ST_AS(is_invocable_r_v<U,O_U,R,U>);}TE <TY R,TY U,TY O_U,TY GROUP> IN AbstractModule<R,U,O_U,GROUP>::AbstractModule(CO R& dummy,O_U o_U,GROUP M):AbstractRSet<R,U,O_U>(dummy,M.One(),MO(o_U)),GROUP(MO(M)){ST_AS(is_same_v<U,inner_t<GROUP>>);}TE <TY U,TY MAGMA> IN U RegularRSet<U,MAGMA>::Action(CO U& r,U u){RE TH->Product(r,MO(u));}TE <TY R,TY U,TY O_U> IN U AbstractRSet<R,U,O_U>::Action(CO R& r,U u){RE m_o_U(r,MO(u));}TE <TY R,TY U> IN U Module<R,U>::Action(CO R& r,U u){RE MO(u *= r);}TE <TY R,TY U> IN U VirtualRSet<R,U>::PW(U u,CO R& r){RE Action(r,MO(u));}TE <TY R,TY U> IN U VirtualRSet<R,U>::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<is_invocable_r_v<bool,F,U,int>>*

TE <TY U,TY NON_COMM_N_MODULE>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<U> m_a;VE<U> m_b;VE<U> m_lazy_substitution;VE<bool> 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<U> a);IN IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE<U> a,CRI N_sqrt);TE <TY...Args> 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 <TY F,SFINAE_FOR_SD_S = nullptr> 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 <TY F> int Search_Body(CRI i_start,CO F& f,U sum_temp);};TE <TY NON_COMM_N_MODULE,TY...Args> IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,Args&&... args)-> IntervalSetSqrtDecomposition<inner_t<NON_COMM_N_MODULE>,NON_COMM_N_MODULE>;
TE <TY U,TY NON_COMM_N_MODULE> IN IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,CRI N):IntervalSetSqrtDecomposition(MO(M),N,Sqrt(N)){}TE <TY U,TY NON_COMM_N_MODULE> IN IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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<U,int> && is_same_v<U,inner_t<NON_COMM_N_MODULE>>);}TE <TY U,TY NON_COMM_N_MODULE> IN IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE<U> a):IntervalSetSqrtDecomposition(MO(M),MO(a),Sqrt(a.SZ())){}TE <TY U,TY NON_COMM_N_MODULE> IN IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::IntervalSetSqrtDecomposition(NON_COMM_N_MODULE M,VE<U> 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<U,int> && is_same_v<U,inner_t<NON_COMM_N_MODULE>>);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 <TY U,TY NON_COMM_N_MODULE> TE <TY...Args> IN VO IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::Initialise(Args&&... args){IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE> temp{m_M,forward<Args>(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 <TY U,TY NON_COMM_N_MODULE> IN VO IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::Set(CRI i,CO U& u){IntervalSet(i,i,u);}TE <TY U,TY NON_COMM_N_MODULE> IN VO IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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<bool>::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<bool>::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 <TY U,TY NON_COMM_N_MODULE> IN VO IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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 <TY U,TY NON_COMM_N_MODULE> IN U IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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 <TY U,TY NON_COMM_N_MODULE> IN U IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::Get(CRI i){RE OP[](i);}TE <TY U,TY NON_COMM_N_MODULE> IN U IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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 <TY U,TY NON_COMM_N_MODULE> IN U IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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 <TY U,TY NON_COMM_N_MODULE> TE <TY F,SFINAE_FOR_SD_S> IN int IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::Search(CRI i_start,CO F& f){RE Search_Body(i_start,f,m_M.One());}TE <TY U,TY NON_COMM_N_MODULE> IN int IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::Search(CRI i_start,CO U& u){RE Search(i_start,[&](CO U& product,CRI){RE !(u < product);});}TE <TY U,TY NON_COMM_N_MODULE> TE <TY F> int IntervalSetSqrtDecomposition<U,NON_COMM_N_MODULE>::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<LL> A( N ); SET_A( A , N );
#endif
#include <bits/stdc++.h>
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<double>( chrono::duration_cast<chrono::microseconds>( 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<decldecay_t( MAX )> 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<decltype(VAR)>
TE <TY F,TY...Args> US ret_t = decltype(declval<F>()(declval<Args>()...));
TE <TY T> 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 <TY INT> US T2 = pair<INT,INT>;
TE <TY INT> US T3 = tuple<INT,INT,INT>;
TE <TY INT> US T4 = tuple<INT,INT,INT,INT>;
US path = pair<int,ll>;

// 入出力用
#define DF_OF_COUT_FOR_VE(V)TE <CL Traits,TY Arg> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO V<Arg>& arg){auto BE = arg.BE(),EN = arg.EN();auto IT = BE;WH(IT != EN){(IT == BE?os:os << " ")<< *IT;IT++;}RE os;}
TE <CL Traits> IN basic_istream<char,Traits>& VariadicCin(basic_istream<char,Traits>& is){RE is;}
TE <CL Traits,TY Arg,TY... ARGS> IN basic_istream<char,Traits>& VariadicCin(basic_istream<char,Traits>& is,Arg& arg,ARGS&... args){RE VariadicCin(is >> arg,args...);}
TE <CL Traits> IN basic_istream<char,Traits>& VariadicGetline(basic_istream<char,Traits>& is,CO char& separator){RE is;}
TE <CL Traits,TY Arg,TY... ARGS> IN basic_istream<char,Traits>& VariadicGetline(basic_istream<char,Traits>& 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 <CL Traits,TY Arg1,TY Arg2> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO pair<Arg1,Arg2>& arg){RE os << arg.first << " " << arg.second;}
TE <CL Traits,TY Arg> IN basic_ostream<char,Traits>& VariadicCout(basic_ostream<char,Traits>& os,CO Arg& arg){RE os << arg;}
TE <CL Traits,TY Arg1,TY Arg2,TY... ARGS> IN basic_ostream<char,Traits>& VariadicCout(basic_ostream<char,Traits>& 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 <TY T> ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE <TY T> ST CE CO bool value = is_same_v< decltype(Check(declval<T>())),true_type >;};
TE <TY T , TY U>US Map = conditional_t<is_COructible_v<unordered_map<T,int>>,unordered_map<T,U>,conditional_t<is_ordered::value<T>,map<T,U>,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 <TY U> IN CO U& VirtualPointedSet<U>::POINT()CO NE{RE Point();}
#define DF_OF_POINT(POINT)TE <TY U> IN U& VirtualPointedSet<U>::POINT()NE{RE Point();}
TE <TY U>CL UnderlyingSet{PU:US type = U;};TE <TY U>CL VirtualPointedSet:VI PU UnderlyingSet<U>{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 <TY U>CL PointedSet:VI PU VirtualPointedSet<U>{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE <TY U>CL VirtualNSet:VI PU UnderlyingSet<U>{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE <TY U,TY F_U>CL AbstractNSet:VI PU VirtualNSet<U>{PU:F_U m_f_U;IN AbstractNSet(F_U f_U);IN U Transfer(CO U& u);};TE <TY U>CL VirtualMagma:VI PU UnderlyingSet<U>{PU:VI U Product(U u0,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE <TY U = ll>CL AdditiveMagma:VI PU VirtualMagma<U>{PU:IN U Product(U u0,CO U& u1);};TE <TY U = ll>CL MultiplicativeMagma:VI PU VirtualMagma<U>{PU:IN U Product(U u0,CO U& u1);};TE <TY U,TY M_U>CL AbstractMagma:VI PU VirtualMagma<U>{PU:M_U m_m_U;IN AbstractMagma(M_U m_U);IN U Product(U u0,CO U& u1);};
TE <TY U> IN PointedSet<U>::PointedSet(U b_U):m_b_U(MO(b_U)){}TE <TY U> IN CO U& PointedSet<U>::Point()CO NE{RE m_b_U;}TE <TY U> IN U& PointedSet<U>::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 <TY U,TY F_U> IN AbstractNSet<U,F_U>::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v<U,F_U,U>);}TE <TY U,TY F_U> IN U AbstractNSet<U,F_U>::Transfer(CO U& u){RE m_f_U(u);}TE <TY U> IN U VirtualNSet<U>::Inverse(CO U& u){RE Transfer(u);}TE <TY U,TY M_U> IN AbstractMagma<U,M_U>::AbstractMagma(M_U m_U):m_m_U(MO(m_U)){ST_AS(is_invocable_r_v<U,M_U,U,U>);}TE <TY U> IN U AdditiveMagma<U>::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE <TY U> IN U MultiplicativeMagma<U>::Product(U u0,CO U& u1){RE MO(u0 *= u1);}TE <TY U,TY M_U> IN U AbstractMagma<U,M_U>::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE <TY U> IN U VirtualMagma<U>::Sum(U u0,CO U& u1){RE Product(MO(u0),u1);}TE <TY U>CL VirtualMonoid:VI PU VirtualMagma<U>,VI PU VirtualPointedSet<U>{};TE <TY U = ll>CL AdditiveMonoid:VI PU VirtualMonoid<U>,PU AdditiveMagma<U>,PU PointedSet<U>{};TE <TY U = ll>CL MultiplicativeMonoid:VI PU VirtualMonoid<U>,PU MultiplicativeMagma<U>,PU PointedSet<U>{PU:IN MultiplicativeMonoid(U e_U);};TE <TY U,TY M_U>CL AbstractMonoid:VI PU VirtualMonoid<U>,PU AbstractMagma<U,M_U>,PU PointedSet<U>{PU:IN AbstractMonoid(M_U m_U,U e_U);};TE <TY U> IN MultiplicativeMonoid<U>::MultiplicativeMonoid(U e_U):PointedSet<U>(MO(e_U)){}TE <TY U,TY M_U> IN AbstractMonoid<U,M_U>::AbstractMonoid(M_U m_U,U e_U):AbstractMagma<U,M_U>(MO(m_U)),PointedSet<U>(MO(e_U)){}TE <TY U>CL VirtualGroup:VI PU VirtualMonoid<U>,VI PU VirtualPointedSet<U>,VI PU VirtualNSet<U>{};TE <TY U = ll>CL AdditiveGroup:VI PU VirtualGroup<U>,PU AdditiveMonoid<U>{PU:IN U Transfer(CO U& u);};TE <TY U,TY M_U,TY I_U>CL AbstractGroup:VI PU VirtualGroup<U>,PU AbstractMonoid<U,M_U>,PU AbstractNSet<U,I_U>{PU:IN AbstractGroup(M_U m_U,U e_U,I_U i_U);};TE <TY U,TY M_U,TY I_U> IN AbstractGroup<U,M_U,I_U>::AbstractGroup(M_U m_U,U e_U,I_U i_U):AbstractMonoid<U,M_U>(MO(m_U),MO(e_U)),AbstractNSet<U,I_U>(MO(i_U)){}TE <TY U> IN U AdditiveGroup<U>::Transfer(CO U& u){RE -u;}
// AAA 常設ライブラリは以上に挿入する。

#define INCLUDE_LIBRARY
#include __FILE__

#endif // INCLUDE_LIBRARY

#endif // INCLUDE_SUB

#endif // INCLUDE_MAIN
yukicoder

結果

ソースコード
