#942309 (C++17(gcc12)) No.3579 区間積逆像

提出ソース
結果

問題	No.3579 区間積逆像
コンテスト
ユーザー	👑 p-adic
提出日時	2024-01-08 22:19:38
言語	C++17(gcc12) (gcc 12.4.0 + boost 1.89.0) コンパイル: `g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	28 ms / 2,000 ms
コード長	39,321 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	2,545 ms
コンパイル使用メモリ	251,176 KB
実行使用メモリ	12,496 KB
最終ジャッジ日時	2026-07-03 20:56:36
合計ジャッジ時間	4,116 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 入力制約チェック
#ifndef INCLUDE_MODE
  #define INCLUDE_MODE
  // #define REACTIVE
  // #define USE_GETLINE
#endif

#ifdef INCLUDE_MAIN

inline void Solve()
{
  CEXPR( ll , bound_N , 1e5 );
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( ll , bound_P , 1e9 );
  CIN_ASSERT( P , 1 , bound_P );
  FOR( i , 2 , P ){
    if( i * i > P ){
      break;
    }
    assert( P % i != 0 );
  }
  CIN_ASSERT( C , 0 , P - 1 );
  using ModP = QuotientRing<ll>;
  ModP::SetModulo( &P );
  vector<vector<ModP>> A( 1 );
  FOR( i , 0 , N ){
    CIN_ASSERT( Ai , 0 , P - 1 );
    if( Ai == 0 ){
      A.push_back( {} );
    } else {
      A.back().push_back( Ai );
    }
  }
  ll answer = 0;
  if( C == 0 ){
    FOR_ITR( A ){
      ll size = itr->size();
      answer += size * ( size + 1 ) / 2;
    }
    answer = N * ( N + 1 ) / 2 - answer;
  } else {
    FOR_ITR( A ){
      AbstractCumulativeProduct cp{ AbstractGroup( Multiplication<ModP> , ModP( 1 ) , Id<ModP> ) , *itr };
      answer += cp.CountRightIntervalProductInverseImage( C );
    }
  }
  RETURN( answer );
}
REPEAT_MAIN(1);

#else // INCLUDE_MAIN

#ifdef INCLUDE_LIBRARY

// https://github.com/p-adic/cpp
// VVV ライブラリは以下に挿入する。

// インスタンスごとに異なる法を定めたい場合は
// MultiBase/a.hpp
// のクラスを用いる。
template <typename INT>
class QuotientRing
{

protected:
  INT m_n;
  static const INT* g_p_M;

public:
  inline QuotientRing() noexcept;
  inline QuotientRing( const INT& n ) noexcept;
  inline QuotientRing( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing( QuotientRing<INT>&& n ) noexcept;

  inline QuotientRing<INT>& operator=( QuotientRing<INT> n ) noexcept;
  inline QuotientRing<INT>& operator+=( const QuotientRing<INT>& n ) noexcept;
  // operator<が定義されていても負の数は正に直さず剰余を取ることに注意。
  inline QuotientRing<INT>& operator-=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator*=( const QuotientRing<INT>& n ) noexcept;
  // *g_p_Mが素数でかつnの逆元が存在する場合のみサポート。
  inline QuotientRing<INT>& operator/=( QuotientRing<INT> n );

  // m_nの正負込みの等号。
  inline bool operator==( const QuotientRing<INT>& n ) const noexcept;
  // m_nの正負込みの等号。
  inline bool operator!=( const QuotientRing<INT>& n ) const noexcept;

  inline QuotientRing<INT> operator+( QuotientRing<INT> n1 ) const noexcept;
  inline QuotientRing<INT> operator-() const noexcept;
  inline QuotientRing<INT> operator-( QuotientRing<INT> n1 ) const noexcept;
  inline QuotientRing<INT> operator*( QuotientRing<INT> n1 ) const noexcept;
  // *g_p_Mが素数でかつn1の逆元が存在する場合のみサポート。
  inline QuotientRing<INT> operator/( const QuotientRing<INT>& n1 ) const;
  template <typename T> QuotientRing<INT> operator^( T exponent );

  inline const INT& Represent() const noexcept;
  static inline const INT& GetModulo() noexcept;
  static inline void SetModulo( const INT* const& p_M ) noexcept;

  // *g_p_Mが素数でかつnの逆元が存在する場合のみサポート。
  static QuotientRing<INT> Inverse( const QuotientRing<INT>& n );
  
};

template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , T exponent );
// *g_p_Mが素数でかつnの逆元が存在する場合のみサポート。
template <typename INT> inline QuotientRing<INT> Inverse( const QuotientRing<INT>& n );

template <typename INT , class Traits> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , QuotientRing<INT>& n );
template <typename INT , class Traits> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const QuotientRing<INT>& n );

template <typename INT> const INT* QuotientRing<INT>::g_p_M = nullptr;
template <typename INT> inline QuotientRing<INT>::QuotientRing() noexcept : m_n() {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( const INT& n ) noexcept : m_n( n % *g_p_M ) {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( const QuotientRing<INT>& n ) noexcept : m_n( n.m_n ) {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( QuotientRing<INT>&& n ) noexcept : m_n( move( n.m_n ) ) {}

template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator=( QuotientRing<INT> n ) noexcept { m_n = move( n.m_n ); return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const QuotientRing<INT>& n ) noexcept { ( m_n += n.m_n ) %= *g_p_M; return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const QuotientRing<INT>& n ) noexcept { ( m_n -= n.m_n ) %= *g_p_M; return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const QuotientRing<INT>& n ) noexcept { ( m_n *= n.m_n ) %= *g_p_M; return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator/=( QuotientRing<INT> n ) { return *this *= Inverse( n ); }

template <typename INT> inline bool QuotientRing<INT>::operator==( const QuotientRing<INT>& n ) const noexcept { return m_n == n.m_n; }
template <typename INT> inline bool QuotientRing<INT>::operator!=( const QuotientRing<INT>& n ) const noexcept { return !( *this == n ); }

template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::operator+( QuotientRing<INT> n ) const noexcept { return move( n += *this ); }
template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::operator-() const noexcept { QuotientRing<INT> answer{}; answer.m_n = -answer.m_n; return answer; }
template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::operator-( QuotientRing<INT> n ) const noexcept { return n -= *this; }
template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::operator*( QuotientRing<INT> n ) const noexcept { return n *= *this; }
template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::operator/( const QuotientRing<INT>& n ) const { return Inverse( n ) *= *this; }

template <typename INT> template <typename T>
QuotientRing<INT> QuotientRing<INT>::operator^( T exponent )
{

  QuotientRing<INT> answer{ 1 };
  QuotientRing<INT> power{ *this };
  exponent < 0 ? ( exponent = -exponent , power = Inverse( power ) ) : power;

  while( exponent > 0 ){

    if( ( exponent & 2 ) == 1 ){

      answer *= power;

    }

    power *= power;
    exponent >>= 1;

  }

  return answer;

}

template <typename INT> inline const INT& QuotientRing<INT>::Represent() const noexcept { return m_n; }
template <typename INT> inline const INT& QuotientRing<INT>::GetModulo() noexcept { ssert( g_p_M != nullptr ); return *g_p_M; }
template <typename INT> inline void QuotientRing<INT>::SetModulo( const INT* const& p_M ) noexcept { assert( ( g_p_M = p_M ) != nullptr ); }

template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::Inverse( const QuotientRing<INT>& n ) { return n ^ ( *g_p_M - 2 ); }

template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , T exponent ) { return QuotientRing<INT>::template Power<T>( n , exponent ); }
template <typename INT> inline QuotientRing<INT> Inverse( const QuotientRing<INT>& n ) { return QuotientRing<INT>::Inverse( n ); }

template <typename INT , class Traits> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , QuotientRing<INT>& n ) { INT m; is >> m; n = m; return is; }
template <typename INT , class Traits> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const QuotientRing<INT>& n ) { return os << n.Represent(); }


class is_ordered
{

private:
  is_ordered() = delete;
  template <typename T> static constexpr auto Check( const T& t ) -> decltype( t < t , true_type() );
  static constexpr false_type Check( ... );

public:
  template <typename T> static constexpr const bool value = is_same_v< decltype( Check( declval<T>() ) ) , true_type >;

};


template <typename INT , template <typename...> typename T>
struct hash<T<INT>> :
  public hash<INT>
{

  inline size_t operator()( const T<INT>& n ) const;

};

template <typename T , typename U>
using Map = conditional_t<is_constructible_v<unordered_map<T,int>>,unordered_map<T,U>,conditional_t<is_ordered::value<T>,map<T,U>,void>>;
// Map<T,U>は
// - unordered_map<T,U>()がwell-formedならばunordered_map<T,U>
// - そうでなくoperator<(declval<T>(),declval<T>())がwell-formedならばmap<T,U>
// - そうでないならばvoid

template <typename INT , template <typename...> typename T> inline size_t hash<T<INT>>::operator()( const T<INT>& n ) const { return hash<INT>::operator()( n.Represent() ); }


#define DECLARATION_OF_CPOINT( POINT ) inline const U& POINT() const noexcept
#define DECLARATION_OF_POINT( POINT ) inline U& POINT() noexcept
#define DEFINITION_OF_CPOINT( POINT ) template <typename U> inline const U& VirtualPointedSet<U>::POINT() const noexcept { return Point(); }
#define DEFINITION_OF_POINT( POINT ) template <typename U> inline U& VirtualPointedSet<U>::POINT() noexcept { return Point(); }

// - インタフェースをなるべく抽象型で与えて仮想継承する。
//   - 具体的構造が２種類以上あるものはもちろん抽象型を仮想継承する。
//   - VirtualPointedSetのように具体的構造が１種類しかないものも仮想継承のコンストラクタ呼び出しを
//     省略するためになるべく抽象型を用意する。
//   - AbstractDijkstraのように全ての具体的構造が１つの具体的構造の派生である場合は
//     インタフェースを必要としない。
// - コンストラクタはなるべく省略できるようにするが、ポインタはメンバ変数にしない。
//   - VirtualGraphのように具体的構造が２種類以上あるもので全てに共通の定義本体を持つ関数（Edge）が
//     必要な場合は実装が膨れ上がらないように抽象型に関数の定義をし、そのため抽象型にメンバ変数が
//     必要になる場合はコンストラクタを非自明なものにする
//   - 代わりにポインタを抽象型のメンバとして
//     派生クラスのコンストラクタの定義内でアドレスを渡すようにすると、ムーブなどで意図せず
//     ポインタの指すアドレスが意図通りでなくなることに注意する。
// - データ構造に渡すことを想定する。
//   - データ構造の配列や初期化をムーブセマンティクスで処理できるようにするために
//     代数構造もムーブコンストラクタがdeleteされないようにする。
//   - そのために演算に対応する関数オブジェクトは参照ではなく実体としてメンバに持つ。
template <typename U>
class UnderlyingSet
{

public:
  using type = U;

};

template <typename U>
class VirtualPointedSet :
  virtual public UnderlyingSet<U>
{

public:
  virtual const U& Point() const noexcept = 0;
  virtual U& Point() noexcept = 0;
  DECLARATION_OF_CPOINT( Unit );
  DECLARATION_OF_CPOINT( Zero );
  DECLARATION_OF_CPOINT( One );
  DECLARATION_OF_CPOINT( Infty );
  DECLARATION_OF_POINT( init );
  DECLARATION_OF_POINT( root );

};

template <typename U>
class PointedSet :
  virtual public VirtualPointedSet<U>
{

private:
  U m_b_U;

public:
  inline PointedSet( const U& b_u = U() );
  inline const U& Point() const noexcept;
  inline U& Point() noexcept;

};

template <typename U>
class VirtualNSet :
  virtual public UnderlyingSet<U>
{

public:
  virtual U Transfer( const U& u ) = 0;
  inline U Inverse( const U& u );

};

template <typename U , typename F_U>
class AbstractNSet :
  virtual public VirtualNSet<U>
{

private:
  F_U m_f_U;

public:
  inline AbstractNSet( F_U f_U );
  inline U Transfer( const U& u );

};

template <typename U>
class VirtualMagma :
  virtual public UnderlyingSet<U>
{

public:
  virtual U Product( const U& u0 , const U& u1 ) = 0;
  inline U Sum( const U& u0 , const U& u1 );

};

template <typename U = ll>
class AdditiveMagma :
  virtual public VirtualMagma<U>
{

public:
  inline U Product( const U& u0 , const U& u1 );

};

template <typename U = ll>
class MultiplicativeMagma :
  virtual public VirtualMagma<U>
{

public:
  inline U Product( const U& u0 , const U& u1 );

};

template <typename U , typename M_U>
class AbstractMagma :
  virtual public VirtualMagma<U>
{

private:
  M_U m_m_U;

public:
  inline AbstractMagma( M_U m_U );
  inline U Product( const U& u0 , const U& u1 );

};

template <typename U> inline PointedSet<U>::PointedSet( const U& b_U ) : m_b_U( b_U ) {}
template <typename U> inline const U& PointedSet<U>::Point() const noexcept { return m_b_U; }
template <typename U> inline U& PointedSet<U>::Point() noexcept { return m_b_U; }
DEFINITION_OF_CPOINT( Unit );
DEFINITION_OF_CPOINT( Zero );
DEFINITION_OF_CPOINT( One );
DEFINITION_OF_CPOINT( Infty );
DEFINITION_OF_POINT( init );
DEFINITION_OF_POINT( root );

template <typename U , typename F_U> inline AbstractNSet<U,F_U>::AbstractNSet( F_U f_U ) : m_f_U( move( f_U ) ) { static_assert( is_invocable_r_v<U,F_U,U> ); }
template <typename U , typename F_U> inline U AbstractNSet<U,F_U>::Transfer( const U& u ) { return m_f_U( u ); }
template <typename U> inline U VirtualNSet<U>::Inverse( const U& u ) { return Transfer( u ); }

template <typename U , typename M_U> inline AbstractMagma<U,M_U>::AbstractMagma( M_U m_U ) : m_m_U( move( m_U ) ) { static_assert( is_invocable_r_v<U,M_U,U,U> ); }


template <typename U> inline U AdditiveMagma<U>::Product( const U& u0 , const U& u1 ) { return u0 + u1; }
template <typename U> inline U MultiplicativeMagma<U>::Product( const U& u0 , const U& u1 ) { return u0 * u1; }
template <typename U , typename M_U> inline U AbstractMagma<U,M_U>::Product( const U& u0 , const U& u1 ) { return m_m_U( u0 , u1 ); }
template <typename U> inline U VirtualMagma<U>::Sum( const U& u0 , const U& u1 ) { return Product( u0 , u1 ); }

template <typename U>
class VirtualMonoid :
  virtual public VirtualMagma<U> ,
  virtual public VirtualPointedSet<U>
{};

template <typename U = ll>
class AdditiveMonoid :
  virtual public VirtualMonoid<U> ,
  public AdditiveMagma<U> ,
  public PointedSet<U>
{};

template <typename U = ll>
class MultiplicativeMonoid :
  virtual public VirtualMonoid<U> ,
  public MultiplicativeMagma<U> ,
  public PointedSet<U>
{

public:
  inline MultiplicativeMonoid( const U& e_U );

};

template <typename U , typename M_U>
class AbstractMonoid :
  virtual public VirtualMonoid<U> ,
  public AbstractMagma<U,M_U> ,
  public PointedSet<U>
{

public:
  inline AbstractMonoid( M_U m_U , const U& e_U );

};

template <typename U> inline MultiplicativeMonoid<U>::MultiplicativeMonoid( const U& e_U ) : PointedSet<U>( e_U ) {}
template <typename U , typename M_U> inline AbstractMonoid<U,M_U>::AbstractMonoid( M_U m_U , const U& e_U ) : AbstractMagma<U,M_U>( move( m_U ) ) , PointedSet<U>( e_U ) {}

template <typename U>
class VirtualGroup :
  virtual public VirtualMonoid<U> ,
  virtual public VirtualPointedSet<U> ,
  virtual public VirtualNSet<U>
{};

template <typename U = ll>
class AdditiveGroup :
  virtual public VirtualGroup<U> ,
  public AdditiveMonoid<U>
{

public:
  inline U Transfer( const U& u );

};

template <typename U , typename M_U , typename I_U>
class AbstractGroup :
  virtual public VirtualGroup<U> ,
  public AbstractMonoid<U,M_U> ,
  public AbstractNSet<U,I_U>
{

public:
  inline AbstractGroup( M_U m_U , const U& e_U , I_U i_U );

};

template <typename U , typename M_U , typename I_U> inline AbstractGroup<U,M_U,I_U>::AbstractGroup( M_U m_U , const U& e_U , I_U i_U ) : AbstractMonoid<U,M_U>( move( m_U ) , e_U ) , AbstractNSet<U,I_U>( move( i_U ) ) {}

template <typename U> inline U AdditiveGroup<U>::Transfer( const U& u ) { return -u; }


// static_assertではU=llの時にintが渡された時にコンパイルエラーとなる。
#define SFINAE_FOR_CP_BS enable_if_t<is_invocable_r_v<bool,F,U,int>>*

// 木上で群に値を持つ関数の累積積を計算する。
template <typename U>
class VirtualCumulativeProduct
{

public:
  // 0 <= i,j < m_sizeの場合のみサポート。
  // iからへのpathがi=v_0->...->v_k=jの時、初期化に用いた配列aに対する
  // 右総乗a[v_0]...a[v_k]を計算する。
  virtual U PathProduct( const int& i , const int& j ) = 0;

protected:
  virtual int Parent( const int& i ) = 0;
  virtual int LCA( const int& i , const int& j ) = 0;

};

template <typename U , typename GROUP>
class PathProductImplementation :
  virtual public VirtualCumulativeProduct<U>
{

protected:
  GROUP m_M;
  int m_size;
  vector<U> m_right;
  vector<U> m_left;

public:
  inline PathProductImplementation( GROUP M , const int& size );
  inline U PathProduct( const int& i_start , const int& i_final );

};

// 木が特に通常の配列である場合。
// 入力の範囲内で要件
// (1) MがUの群構造である。
// が成り立つ場合にのみサポート。
// ただし区間積か区間積の二分探索を用いない場合はモノイド構造でよい。

// M.one()による初期化O(size)（モノイド構造を使う）
// 配列による初期化O(size)（半群構造を使う）

// 一点代入O(size)（半群構造を使う）
// 一点右乗算O(size)（半群構造を使う）
// 一点左乗算O(size)（半群構造を使う）

// 右始切片積取得O(1)（モノイド構造を使う）
// 左始切片積取得O(1)（モノイド構造を使う）

// 右区間積取得O(1)（群構造を使う）
// 左区間積取得O(1)（群構造を使う）

// 右区間積逆像数え上げO(size log size)（半群構造を使う）
// 左区間積逆像数え上げO(size log size)（半群構造を使う）

// 以下は入力の範囲内で要件
// (2) operator<(const U&,const U&)に関してMがUの全順序群構造である。
// (3) 各成分がM.One()より小さくない。
// を満たす場合にのみサポート。
// 左始切片積がu以上となる要素の添字の最小値の二分探索O(log_2 size)（全順序モノイド構造を使う）
// 右始切片積がu以上となる要素の添字の最小値の二分探索O(log_2 size)（全順序モノイド構造を使う）
// 左区間積がu以上となる要素の添字の最小値の二分探索O(log_2 size)（全順序群構造を使う）
// 右区間積がu以上となる要素の添字の最小値の二分探索O(log_2 size)（全順序群構造を使う）
template <typename U , typename GROUP>
class AbstractCumulativeProduct :
  public PathProductImplementation<U,GROUP>
{

private:
  vector<U> m_a;

public:
  inline AbstractCumulativeProduct( GROUP M , const int& size = 0 );
  inline AbstractCumulativeProduct( GROUP M , vector<U> a );

  inline void Reset( const vector<U>& a );
  // a[i]をuに置き変える。
  inline void Set( const int& i , const U& u );
  // a[i]をM.Product(a[i],u)に置き変える。
  inline void RightMultiply( const int& i , const U& u );
  // a[i]をM.Product(u,a[i])に置き変える。
  inline void LeftMultiply( const int& i , const U& u );

  // 0 <= i_final < m_sizeの場合のみサポート。
  // 右始切片積a[0]...a[i_final]をMに関して計算する。
  inline const U& RightInitialSegmentProduct( int i_final );
  // 左始切片積a[i_final]...a[0]をMに関して計算する。
  inline const U& LeftInitialSegmentProduct( int i_final );

  // 0 <= i_startかつi_start-1 <= i_final < m_sizeの場合のみサポート。
  // 右区間積a[i_start]...a[i_final]をMに関して計算する。
  inline U RightIntervalProduct( const int& i_start , int i_final );
  // 左区間積a[i_final]...a[i_start]をMに関して計算する。
  inline U LeftIntervalProduct( const int& i_start , int i_final );

  // Mに関する右区間積a[i]...a[j]がuと等しい区間[i,j]の個数を計算する。
  ll CountRightIntervalProductInverseImage( const U& u );
  // Mに関する左区間積a[j]...a[i]がuと等しい区間[i,j]の個数を計算する。
  ll CountLeftIntervalProductInverseImage( const U& u );

  // Fは積順序に関して単調な写像f:U \times int -> {0,1}に相当する型。
  // f( RightInitialSegmentProduct( i ) , i )がtrueとなるi_start以上のiが
  // 存在する場合にその最小値を2進法で探索。存在しない場合はNを返す。
  template <typename F , SFINAE_FOR_CP_BS = nullptr> int RightBinarySearch( const F& f );
  // f( LeftInitialSegmentProduct( i ) , i )がtrueとなるi_start以上のiが
  // 存在する場合にその最小値を2進法で探索。存在しない場合はNを返す。
  template <typename F , SFINAE_FOR_CP_BS = nullptr> int LeftBinarySearch( const F& f );
  // f( RightIntervalProduct( i_start , i ) , i )がtrueとなるi_start以上のiが
  // 存在する場合にその最小値を2進法で探索。存在しない場合はNを返す。
  template <typename F , SFINAE_FOR_CP_BS = nullptr> int RightBinarySearch( const int& i_start , const F& f );
  // f( LeftIntervalProduct( i_start , i ) , i )がtrueとなるi_start以上のiが
  // 存在する場合にその最小値を2進法で探索。存在しない場合はNを返す。
  template <typename F , SFINAE_FOR_CP_BS = nullptr> int LeftBinarySearch( const int& i_start , const F& f );
  // RightInitialSegmentProduct( i )がu以上となるiが存在する場合にその最小値を2進法で探索。
  // 存在しない場合はNを返す。
  int RightBinarySearch( const U& u );
  // LeftInitialSegmentProduct( i )がu以上となるiが存在する場合にその最小値を2進法で探索。
  // 存在しない場合はNを返す。
  int LeftBinarySearch( const U& u );
  // RightIntervalProduct( i_start , i )がu以上となるi_start以上のiが存在する場合に
  // その最小値を2進法で探索。存在しない場合はNを返す。
  int RightBinarySearch( const int& i_start , const U& u );
  // LeftIntervalProduct( i_start , i )がu以上となるi_start以上のiが存在する場合に
  // その最小値を2進法で探索。存在しない場合はNを返す。
  int LeftBinarySearch( const int& i_start , const U& u );
  
private:
  inline int Parent( const int& i );
  inline int LCA( const int& i , const int& j );

};
template <typename GROUP , typename...Args> AbstractCumulativeProduct( GROUP M , const Args&... args ) -> AbstractCumulativeProduct<inner_t<GROUP>,GROUP>;

template <typename U>
class CumulativeSum :
  public AbstractCumulativeProduct<U,AdditiveGroup<U>>
{

public:
  inline CumulativeSum( const int& size = 0 );
  inline CumulativeSum( vector<U> a );

  // a[i]をM.Sum(u,a[i])に置き変える。
  inline void Add( const int& i , const U& u );

  // 始切片和a[0]+...+a[i_final]を計算する。
  inline const U& InitialSegmentSum( int i_final );

  // 区間和a[i_start]+...+a[i_final]を計算する。
  inline U IntervalSum( const int& i_start , int i_final );

  // 区間和a[i]+...+a[j]がuと等しい区間[i,j]の個数を計算する。
  ll CountIntervalSumInverseImage( const U& u = U() );

  template <typename...Args> int BinarySearch( const Args&... args );

};

// 乗法群に使いたい状況と乗法モノイドに使いたい状況が同程度であるため
// 非AbstractなCumulativeProductは定義せずAbstractを使う。

template <typename U , typename GROUP> inline PathProductImplementation<U,GROUP>::PathProductImplementation( GROUP M , const int& size ) : m_M( move( M ) ) , m_size( size ) , m_right( m_size , m_M.One() ) , m_left( m_right ) {}
template <typename U , typename GROUP> inline AbstractCumulativeProduct<U,GROUP>::AbstractCumulativeProduct( GROUP M , const int& size ) : AbstractCumulativeProduct( M , vector<U>( size , M.One() ) ) {}
template <typename U , typename GROUP> inline AbstractCumulativeProduct<U,GROUP>::AbstractCumulativeProduct( GROUP M , vector<U> a ) : PathProductImplementation<U,GROUP>( move( M ) , a.size() ) , m_a( move( a ) )
{

  if( !m_a.empty() ){

    this->m_right[0] = this->m_left[0] = m_a[0];

    for( int i = 1 ; i < this->m_size ; i++ ){

      this->m_right[i] = this->m_M.Product( this->m_right[i-1] , m_a[i] );
      this->m_left[i] = this->m_M.Product( m_a[i] , this->m_left[i-1] );

    }

  }

}

template <typename U> inline CumulativeSum<U>::CumulativeSum( const int& size ) : CumulativeSum( vector<U>( size ) ){}
template <typename U> inline CumulativeSum<U>::CumulativeSum( vector<U> a ) : AbstractCumulativeProduct<U,AdditiveGroup<U>>( AdditiveGroup<U>() , move( a ) ) {}

template <typename U , typename GROUP> inline void AbstractCumulativeProduct<U,GROUP>::Reset( const vector<U>& a ) { *this = AbstractCumulativeProduct( move( this->m_M ) , a ); }

template <typename U , typename GROUP> inline void AbstractCumulativeProduct<U,GROUP>::Set( const int& i , const U& u )
{

  assert( 0 <= i && i < this->_size );
  m_a[i] = u;

  if( i == 0 ){

    this->m_right[0] = this->m_left[0] = m_a[0];

  }
  
  for( int j = max( i , 1 ) ; j < this->m_size ; j++ ){

    this->m_right[j] = this->m_M.Product( this->m_right[j-1] , m_a[j] );
    this->m_left[j] = this->m_M.Product( m_a[j] , this->m_left[j-1] );

  }

}

template <typename U , typename GROUP> inline void AbstractCumulativeProduct<U,GROUP>::RightMultiply( const int& i , const U& u ) { Set( i , this->m_M.Product( m_a[i] , u ) ); }

template <typename U , typename GROUP> inline void AbstractCumulativeProduct<U,GROUP>::LeftMultiply( const int& i , const U& u ) { Set( i , this->m_M.Product( u , m_a[i] ) ); }

template <typename U> inline void CumulativeSum<U>::Add( const int& i , const U& u ) { this->RightMultiply( i , u ); }

template <typename U , typename GROUP> inline U PathProductImplementation<U,GROUP>::PathProduct( const int& i_start , const int& i_final ) { assert( 0 <= i_start && i_start < m_size && 0 <= i_final && i_final < m_size ); const int k = this->LCA( i_start , i_final ); return m_M.Product( m_M.Product( m_left[i_start] , m_M.Inverse( m_left[k] ) ) , k == 0 ? m_right[i_final] : m_M.Product( m_M.Inverse( m_right[this->Parent( k ) ] ) , m_right[i_final] )); }

template <typename U , typename GROUP> inline const U& AbstractCumulativeProduct<U,GROUP>::RightInitialSegmentProduct( int i_final ) { i_final = min( i_final , this->m_size - 1 ); return 0 <= i_final ? this->m_right[i_final] : this->m_M.One(); }
template <typename U , typename GROUP> inline const U& AbstractCumulativeProduct<U,GROUP>::LeftInitialSegmentProduct( int i_final ) { i_final = min( i_final , this->m_size - 1 ); return 0 <= i_final ? this->m_left[i_final] : this->m_M.One();; }
template <typename U> inline const U& CumulativeSum<U>::InitialSegmentSum( int i_final ) { return this->RightInitialSegmentProduct( move( i_final ) ); }

template <typename U , typename GROUP> inline U AbstractCumulativeProduct<U,GROUP>::RightIntervalProduct( const int& i_start , int i_final ) { i_final = min( i_final , this->m_size - 1 ); return i_start <= i_final ? i_start <= 0 ? this->m_right[i_final] : this->m_M.Product( this->m_M.Inverse( this->m_right[i_start-1] ) , this->m_right[i_final] ) : this->m_M.One(); }
template <typename U , typename GROUP> inline U AbstractCumulativeProduct<U,GROUP>::LeftIntervalProduct( const int& i_start , int i_final ) { i_final = min( i_final , this->m_size - 1 ); return i_start <= i_final ? i_start <= 0 ? this->m_left[i_final] : this->m_M.Product( this->m_left[i_final] , this->m_M.Inverse( this->m_left[i_start - 1] ) ) : this->m_M.One(); }
template <typename U> inline U CumulativeSum<U>::IntervalSum( const int& i_start , int i_final ) { return this->RightIntervalProduct( i_start , move( i_final ) ); }

template <typename U , typename GROUP> ll AbstractCumulativeProduct<U,GROUP>::CountRightIntervalProductInverseImage( const U& u )
{

  Map<U,ll> f{};
  f[u]++;
  ll answer = 0;

  for( int i = 0 ; i < this->m_size ; i++ ){

    const U& m_right_i = this->m_right[i];
    f.count( m_right_i ) == 1 ? answer += f[m_right_i] : answer;
    f[this->m_M.Product( m_right_i , u )]++;

  }

  return answer;

}

template <typename U , typename GROUP> ll AbstractCumulativeProduct<U,GROUP>::CountLeftIntervalProductInverseImage( const U& u )
{

  Map<U,ll> f{};
  f[u]++;
  ll answer = 0;

  for( int i = 0 ; i < this->m_size ; i++ ){

    const U& m_left_i = this->m_left[i];
    f.count( m_left_i ) == 1 ? answer += f[m_left_i] : answer;
    f[this->m_M.Product( u , m_left_i )]++;

  }

  return answer;

}

template <typename U> ll CumulativeSum<U>::CountIntervalSumInverseImage( const U& u ) { return this->CountRightIntervalProductInverseImage( u ); }

template <typename U , typename GROUP> template <typename F , SFINAE_FOR_CP_BS>
int AbstractCumulativeProduct<U,GROUP>::RightBinarySearch( const F& f )
{

  if( f( m_a[0] , 0 ) ){

    return 0;

  }
  
  int l = 0;
  int r = this->m_size;
  
  while( l + 1 < r ){

    int m = ( l + r ) / 2;
    ( f( RightInitialSegmentProduct( m ) , m ) ? r : l ) = m;

  }

  return r;

}

template <typename U , typename GROUP> template <typename F , SFINAE_FOR_CP_BS>
int AbstractCumulativeProduct<U,GROUP>::LeftBinarySearch( const F& f )
{

  if( f( m_a[0] , 0 ) ){

    return 0;

  }
  
  int l = 0;
  int r = this->m_size;
  
  while( l + 1 < r ){

    int m = ( l + r ) / 2;
    ( f( LeftInitialSegmentProduct( m ) , m ) ? r : l ) = m;

  }

  return r;

}

template <typename U , typename GROUP> template <typename F , SFINAE_FOR_CP_BS>
int AbstractCumulativeProduct<U,GROUP>::RightBinarySearch( const int& i_start , const F& f )
{

  if( f( m_a[i_start] , i_start ) ){

    return i_start;

  }
  
  int l = i_start;
  int r = this->m_size;
  
  while( l + 1 < r ){

    int m = ( l + r ) / 2;
    ( f( RightIntervalProduct( i_start , m ) , m ) ? r : l ) = m;

  }

  return r;

}

template <typename U , typename GROUP> template <typename F , SFINAE_FOR_CP_BS>
int AbstractCumulativeProduct<U,GROUP>::LeftBinarySearch( const int& i_start , const F& f )
{

  if( f( m_a[i_start] , i_start ) ){

    return i_start;

  }
  
  int l = i_start;
  int r = this->m_size;
  
  while( l + 1 < r ){

    int m = ( l + r ) / 2;
    ( f( LeftIntervalProduct( i_start , m ) , m ) ? r : l ) = m;

  }

  return r;

}

template <typename U , typename GROUP> inline int AbstractCumulativeProduct<U,GROUP>::RightBinarySearch( const U& u ) { return RightBinarySearch( [&]( const U& prod , const int& i ){ return !( prod < u ); } ); }
template <typename U , typename GROUP> inline int AbstractCumulativeProduct<U,GROUP>::LeftBinarySearch( const U& u ) { return LeftBinarySearch( [&]( const U& prod , const int& i ){ return !( prod < u ); } ); }
template <typename U , typename GROUP> inline int AbstractCumulativeProduct<U,GROUP>::RightBinarySearch( const int& i_start , const U& u ) { return RightBinarySearch( i_start , [&]( const U& prod , const int& i ){ return !( prod < u ); } ); }
template <typename U , typename GROUP> inline int AbstractCumulativeProduct<U,GROUP>::LeftBinarySearch( const int& i_start , const U& u ) { return LeftBinarySearch( i_start , [&]( const U& prod , const int& i ){ return !( prod < u ); } ); }
template <typename U> template <typename...Args> int CumulativeSum<U>::BinarySearch( const Args&... args ) { return this->RightBinarySearch( args... ); }

template <typename U , typename GROUP> inline int AbstractCumulativeProduct<U,GROUP>::Parent( const int& i ) { return i - 1; }
template <typename U , typename GROUP> inline int AbstractCumulativeProduct<U,GROUP>::LCA( const int& i , const int& j ) { return min( i , j ); }

// AAA ライブラリは以上に挿入する。

#define INCLUDE_MAIN
#include __FILE__

#else // INCLUDE_LIBRARY

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 )
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #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 , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
  #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#else
  #define SET_LL( A ) cin >> A
  #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
  #define SET_A( A , N ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ cin >> A[VARIABLE_FOR_SET_A]; }
  #define CIN_A( LL , A , N ) vector<LL> A( N ); SET_A( A , N );
#endif
#include <bits/stdc++.h>
using namespace std;
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( 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 ) constexpr LL BOUND = VALUE
#define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )
#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 .begin() , end_ ## ARRAY = ARRAY .end()
#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.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( 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( ... ) COUT( __VA_ARGS__ ); return

// 型のエイリアス
#define decldecay_t( VAR ) decay_t<decltype( VAR )>
template <typename F , typename...Args> using ret_t = decltype( declval<F>()( declval<Args>()... ) );
template <typename T> using inner_t = typename T::type;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
using path = pair<int,ll>;

// 入出力用
template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const vector<Arg>& arg ) { auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os << " " ) << *itr; itr++; } return os; }
template <class Traits , typename Arg1 , typename Arg2> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const pair<Arg1,Arg2>& arg ) { return os << arg.first << " " << arg.second; }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }

// データ構造用
template <typename T> inline T Multiplication( const T& t0 , const T& t1 ) { return t0 * t1; }
template <typename T> inline T Id( const T& v ) { return v; }

// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
  void AutoCheck( bool& auto_checked );
#endif

#define INCLUDE_LIBRARY
#include __FILE__

#endif // INCLUDE_LIBRARY

#endif // INCLUDE_MAIN
yukicoder

結果

ソースコード
