結果

問題 No.2395 区間二次変換一点取得
コンテスト
ユーザー 👑 p-adic
提出日時 2023-03-28 12:36:18
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 7,311 bytes
コンパイル時間 1,209 ms
コンパイル使用メモリ 101,088 KB
最終ジャッジ日時 2025-02-11 18:48:38
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
using namespace std;

using ll = long long;

#define MAIN main
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0

#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO )		\
  ll ANSWER{ 1 };							\
  {									\
    ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO;	\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\

struct ModB
{
  ll m_n;
  static ll g_B;
  constexpr ModB() : m_n() {};
  inline ModB( const ll& n ) : m_n( n % g_B ) {};
  inline ModB( const ModB& n ) : m_n( n.m_n ) {};
  inline ModB( ModB&& n ) : m_n( move( n.m_n ) ) {};
  inline ModB& operator=( const ModB& n ) { m_n = n.m_n; return *this; }
  inline ModB& operator=( ModB&& n ) { m_n = move( n.m_n ); return *this; }
  inline ModB& operator+=( const ModB& n ) { ( m_n += n.m_n ) < g_B ? m_n : m_n -= g_B; return *this; }
  inline ModB& operator*=( const ll& n ) { ( m_n *= n ) %= g_B; return *this; }
};

ll ModB::g_B = 1;
inline ModB operator+( const ModB& n0 , const ModB& n1 ) { ll n = n0.m_n + n1.m_n; return ModB( n < ModB::g_B ? n : n -= ModB::g_B ); }
inline ModB operator-( const ModB& n ) { return ModB( n.m_n == 0 ? 0 : ModB::g_B - n.m_n ); }
inline ModB operator-( const ModB& n0 , const ModB& n1 ) { ll n = n0.m_n - n1.m_n; return ModB( n < 0 ? n += ModB::g_B : n ); }
inline ModB operator*( const ModB& n0 , const ModB& n1 ) { return ModB( n0.m_n * n1.m_n ); }

template <typename T , int N>
class BIT
{
private:
  T m_fenwick[N + 1];

public:
  inline BIT();
  BIT( const T ( & a )[N] );

  inline void Set( const int& i , const T& n );

  inline BIT<T,N>& operator+=( const T ( & a )[N] );
  void Add( const int& i , const T& n );

  T InitialSegmentSum( const int& i_final );
  inline T IntervalSum( const int& i_start , const int& i_final );
  
};

template <typename T , int N> inline BIT<T,N>::BIT() : m_fenwick() {}
template <typename T , int N>
BIT<T,N>::BIT( const T ( & a )[N] ) : m_fenwick()
{

  for( int j = 1 ; j <= N ; j++ ){

    T& fenwick_j = m_fenwick[j];
    int i = j - 1;
    fenwick_j = a[i];
    int i_lim = j - ( j & -j );

    while( i != i_lim ){

      fenwick_j += m_fenwick[i];
      i -= ( i & -i );

    }

  }

}

template <typename T , int N> inline void BIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }

template <typename T , int N> inline BIT<T,N>& BIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; }

template <typename T , int N>
void BIT<T,N>::Add( const int& i , const T& n )
{
  
  int j = i + 1;

  while( j <= N ){

    m_fenwick[j] += n;
    j += ( j & -j );

  }

  return;
  
}

template <typename T , int N> 
T BIT<T,N>::InitialSegmentSum( const int& i_final )
{

  T sum = 0;
  int j = ( i_final < N ? i_final : N - 1 ) + 1;

  while( j > 0 ){

    sum += m_fenwick[j];
    j -= j & -j;
    
  }

  return sum;
  
}

template <typename T , int N> inline T BIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); }

template <typename T , int N>
class IntervalAddBIT
{
private:
  // 母関数の微分の負の階差数列（(i-1)a_{i-1} - ia_i）の管理
  BIT<T,N> m_bit_0;
  // 階差数列（a_i - a_{i-1}）の管理
  BIT<T,N> m_bit_1;

public:
  inline IntervalAddBIT();
  inline IntervalAddBIT( const T ( & a )[N] );

  inline void Set( const int& i , const T& n );

  inline IntervalAddBIT<T,N>& operator+=( const T ( & a )[N] );
  inline void Add( const int& i , const T& n );
  inline void IntervalAdd( const int& i_start , const int& i_final , const T& n );

  inline T InitialSegmentSum( const int& i_final );
  inline T IntervalSum( const int& i_start , const int& i_final );
  
};

template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT() : m_bit_0() , m_bit_1() {}
template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT( const T ( & a )[N] ) : m_bit_0() , m_bit_1() { operator+=( a ); }

template <typename T , int N> inline void IntervalAddBIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }

template <typename T , int N> inline IntervalAddBIT<T,N>& IntervalAddBIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; }

template <typename T , int N> inline void IntervalAddBIT<T,N>::Add( const int& i , const T& n ) { IntervalAdd( i , i , n ); }

template <typename T , int N> inline void IntervalAddBIT<T,N>::IntervalAdd( const int& i_start , const int& i_final , const T& n ) { m_bit_0.Add( i_start , - ( i_start - 1 ) * n ); m_bit_0.Add( i_final + 1 , i_final * n ); m_bit_1.Add( i_start , n ); m_bit_1.Add( i_final + 1 , - n ); }


template <typename T , int N> inline T IntervalAddBIT<T,N>::InitialSegmentSum( const int& i_final ) { return m_bit_0.InitialSegmentSum( i_final ) + i_final * m_bit_1.InitialSegmentSum( i_final ); }

template <typename T , int N> inline T IntervalAddBIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); }


inline CEXPR( int , bound_N , 100000 );

struct ArrayOne
{
  int m_val[bound_N];
  constexpr ArrayOne() : m_val() { FOR( i , 0 , bound_N ){ m_val[i] = 1; } }
};

int MAIN()
{
  UNTIE;
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( ll , bound_B , 1000000000 );
  CIN_ASSERT( B , 1 , bound_B );
  ModB::g_B = move( B );
  CEXPR( int , bound_Q , 100000 );
  CIN_ASSERT( Q , 1 , bound_Q );
  constexpr ArrayOne X_prep{};
  static IntervalAddBIT<int,bound_N> X{ X_prep.m_val };
  constexpr ll three = 3;
  REPEAT( Q ){
    CIN_ASSERT( L , 1 , N );
    CIN_ASSERT( M , L , N );
    CIN_ASSERT( R , M , N );
    L--;
    M--;
    R--;
    X.IntervalAdd( L , R , 1 );
    ll X_M = X.IntervalSum( M , M );
    POWER_MOD( power , three , X_M - 2 , ModB::g_B );
    ll Y_M = ( power * ( ( ( X_M - 1 ) * ( X_M + 2 ) + 3 ) % ModB::g_B ) ) % ModB::g_B;
    ll Z_M = ( power * 3 ) % ModB::g_B;
    X_M %= ModB::g_B;
    cout << X_M << " " << Y_M << " " << Z_M << "\n";
  }
  QUIT;
}
0