結果
問題 | No.2292 Interval Union Find |
ユーザー | 👑 p-adic |
提出日時 | 2023-05-12 07:39:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 18,051 bytes |
コンパイル時間 | 4,637 ms |
コンパイル使用メモリ | 248,664 KB |
実行使用メモリ | 89,316 KB |
最終ジャッジ日時 | 2024-11-28 01:28:45 |
合計ジャッジ時間 | 44,036 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 6 WA * 38 |
ソースコード
#pragma GCC optimize ( "O3" )#pragma GCC optimize( "unroll-loops" )#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )#include <bits/stdc++.h>using namespace std;using ll = long long;#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 FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )#define QUIT return 0#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"template <int N>class SqrtCalculation{public:int m_val;inline constexpr SqrtCalculation();};template <int N> inline constexpr SqrtCalculation<N>::SqrtCalculation() : m_val( 1 ) { int m_val2 = 1; while( ( m_val2 << 2 ) <= N ){ m_val <<= 1;m_val2 <<= 2; } while( m_val2 < N ){ m_val++; m_val2 = m_val * m_val; } }#define TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION typename T , T m_T(const T&,const T&) , const T& e_T() , typename U , U m_U(const U&,const U&), const U& e_U() , U o_U(const T&,const U&) , int N , int N_sqrt// (結合的とも単位的とも可換とも限らない)基点付きマグマ(T,m_T:T^2->T,e_T:1->T)と// (可換とは限らない)モノイド(U,m_U:U^2->U,e_U:1->U)と// 基点が恒等変換に対応するT作用(o_U:T×U->U)と非負整数Nをパラメータとする。// e_Uによる初期化O(N)// 配列による初期化O(N)// 一点取得O(1)// 区間積取得O(min(i_final-i_start+1,N^{1/2}))(Uのモノイド性を使う)// 一点更新O(N^{1/2})(区間更新とオーダーは同じだが定数倍良い)// 1つの代入値による区間更新O(N^{1/2})// o_Uによる一点更新はなし。// o_Uによる区間更新O(N^{1/2})template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION = SqrtCalculation<N>{}.m_val >class LazySqrtDecomposition{// private:public:static constexpr const int N_d = ( N + N_sqrt - 1 ) / N_sqrt;static constexpr const int N_m = N_d * N_sqrt;U m_a[N_m];U m_b[N_d];U m_lazy_substitution[N_d];bool m_suspended[N_d];T m_lazy_action[N_d];public:static const T& g_e_T;static const U& g_e_U;inline constexpr LazySqrtDecomposition();inline constexpr LazySqrtDecomposition( const U ( &a )[N] );inline constexpr U Get( const int& i ) const;inline constexpr U IntervalProd( const int& i_start , const int& i_final ) const;inline constexpr void Set( const int& i , const U& u );inline constexpr void IntervalSet( const int& i_start , const int& i_final , const U& u );inline constexpr void IntervalAct( const int& i_start , const int& i_final , const T& t );static inline constexpr U Power( const U& u , int exponent );private:inline constexpr U IntervalProd_Body( const int& i_min , const int& i_ulim ) const;inline constexpr void SetProd( const int& i );inline constexpr void SolveSuspension( const int& d , const U& u );inline constexpr void IntervalSet_Body( const int& i_min , const int& i_ulim , const U& t );inline constexpr void IntervalAct_Body( const int& d , T& t );inline constexpr void IntervalAct_Body( const int& i_min , const int& i_ulim , const T& t );};template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> const T& LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::g_e_T = e_T();template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> const U& LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::g_e_U = e_U();template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::LazySqrtDecomposition(): m_a() , m_b() , m_lazy_substitution() , m_suspended() , m_lazy_action(){if( m_a[0] != g_e_U ){for( int d = 0 ; d < N_d ; d++ ){m_b[d] = m_lazy_substitution[d] = g_e_U;m_suspended[d] = true;}}if( m_lazy_action[0] != g_e_T ){for( int d = 0 ; d < N_d ; d++ ){m_lazy_action[d] = g_e_T;}}}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::LazySqrtDecomposition( const U ( &a )[N] ): m_a() , m_b() , m_lazy_substitution() , m_suspended() , m_lazy_action(){int i = 0;while( i < N ){m_a[i] = a[i];i++;}while( i < N_m ){m_a[i] = g_e_U;i++;}i = 0;for( int d = 0 ; d < N_d ; d++ ){U& m_bd = m_b[d] = g_e_U;for( int j = 0 ; j < N_sqrt ; j++ ){m_bd = m_U( m_bd , m_a[i] );i++;}}if( m_lazy_action[0] != g_e_T ){for( int d = 0 ; d < N_d ; d++ ){m_lazy_action[d] = g_e_T;}}}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::Get( const int&i ) const { const int d = i / N_sqrt; return m_suspended[d] ? m_lazy_substitution[d] : o_U( m_lazy_action[d] , m_a[i] ); }template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalProd(const int& i_start , const int& i_final ) const{const int i_min = max( i_start , 0 );const int i_ulim = min( i_final + 1 , N );const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;const int d_1 = max( d_0 , i_ulim / N_sqrt );const int i_0 = min( d_0 * N_sqrt , i_ulim ) ;const int i_1 = max( i_0 , d_1 * N_sqrt );U answer = g_e_U;if( i_min < i_0 ){// この時d_0 > 0になる。answer = m_suspended[d_0-1] ? Power( m_lazy_substitution[d_0-1] , i_0 - i_min ) : o_U( m_lazy_action[d_0-1] , IntervalProd_Body( i_min , i_0 ) );}for( int d = d_0 ; d < d_1 ; d++ ){answer = m_U( answer , o_U( m_lazy_action[d] , m_b[d] ) );}if( i_1 < i_ulim ){// この時d_1 < N_dになる。answer = m_U( answer , m_suspended[d_1] ? Power( m_lazy_substitution[d_1] , i_ulim - i_1 ) : o_U( m_lazy_action[d_1] , IntervalProd_Body( i_1 ,i_ulim ) ) );}return answer;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::Set( constint& i , const U& u ){const int d = i / N_sqrt;const int i_min = d * N_sqrt;const int i_ulim = i_min + N_sqrt;U& m_ai = m_a[i];if( m_suspended[d] ){U& m_lazy_substitution_d = m_lazy_substitution[d];if( m_lazy_substitution_d != u ){SolveSuspension( d , m_lazy_substitution_d );m_ai = u;m_b[d] = m_T( m_T( Power( m_lazy_substitution_d , i - i_min ) , u ) , Power( m_lazy_substitution_d , i_ulim - ( i + 1 ) ) );}} else {T& m_lazy_action_d = m_lazy_action[d];bool update = false;if( m_lazy_action_d == g_e_T ){update = m_ai != u;} else {update = true;IntervalAct_Body( i_min , i_ulim , m_lazy_action_d );m_lazy_action_d = g_e_T;}if( update ){m_ai = u;SetProd( d );}}return;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalSet(const int& i_start , const int& i_final , const U& u ){const int i_min = max( i_start , 0 );const int i_ulim = min( i_final + 1 , N );const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;const int d_1 = max( d_0 , i_ulim / N_sqrt );const int d_0_N_sqrt = d_0 * N_sqrt;const int d_1_N_sqrt = d_1 * N_sqrt;const int i_0 = min( d_0_N_sqrt , i_ulim );const int i_1 = max( i_0 , d_1_N_sqrt );if( i_min < i_0 ){// この時d_0 > 0になる。const int d_0_minus = d_0 - 1;const int d_0_N_sqrt_minus = d_0_N_sqrt - N_sqrt;U& m_bd = m_b[d_0_minus];if( m_suspended[d_0_minus] ){U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];SolveSuspension( d_0_minus , m_lazy_substitution_d );IntervalSet_Body( i_min , i_0 , u );m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_min - d_0_N_sqrt_minus ) , Power( u , i_0 - i_min ) ) , Power( m_lazy_substitution_d ,d_0_N_sqrt - i_0 ) );} else {T& m_lazy_action_d = m_lazy_action[d_0_minus];if( m_lazy_action_d != g_e_T ){IntervalAct_Body( d_0 , m_lazy_action_d );}IntervalSet_Body( i_min , i_0 , u );m_bd = m_U( m_U( IntervalProd_Body( d_0_N_sqrt_minus , i_min ) , Power( u , i_0 - i_min ) ) , IntervalProd_Body( d_0_N_sqrt , i_0 ) );}}const U power = Power( u , N_sqrt );for( int d = d_0 ; d < d_1 ; d++ ){m_b[d] = power;m_lazy_substitution[d] = u;m_suspended[d] = true;m_lazy_action[d] = g_e_T;}if( i_1 < i_ulim ){// この時d_1 < N_dになる。const int d_1_N_sqrt_plus = d_1_N_sqrt + N_sqrt;U& m_bd = m_b[d_1];if( m_suspended[d_1] ){U& m_lazy_substitution_d = m_lazy_substitution[d_1];SolveSuspension( d_1 , m_lazy_substitution_d );IntervalSet_Body( i_1 , i_ulim , u );m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_1 - d_1_N_sqrt ) , Power( u , i_ulim - i_1 ) ) , Power( m_lazy_substitution_d ,d_1_N_sqrt_plus - i_ulim ) );} else {T& m_lazy_action_d = m_lazy_action[d_1];if( m_lazy_action_d != g_e_T ){IntervalAct_Body( d_1 , m_lazy_action_d );}m_bd = m_U( m_U( IntervalProd_Body( d_1_N_sqrt , i_1 ) , Power( u , i_ulim - i_1 ) ) , IntervalProd_Body( d_1_N_sqrt_plus , i_1 ) );}}return;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalAct(const int& i_start , const int& i_final , const T& t ){if( t != g_e_T ){const int i_min = max( i_start , 0 );const int i_ulim = min( i_final + 1 , N );const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;const int d_1 = max( d_0 , i_ulim / N_sqrt );const int d_0_N_sqrt = d_0 * N_sqrt;const int d_1_N_sqrt = d_1 * N_sqrt;const int i_0 = min( d_0_N_sqrt , i_ulim );const int i_1 = max( i_0 , d_1_N_sqrt );if( i_min < i_0 ){// この時d_0 > 0になる。const int d_0_minus = d_0 - 1;const int d_0_N_sqrt_minus = d_0_N_sqrt - N_sqrt;U& m_bd = m_b[d_0_minus];if( m_suspended[d_0_minus] ){U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];const U u = o_U( t , m_lazy_substitution_d );SolveSuspension( d_0_minus , m_lazy_substitution_d );IntervalSet_Body( i_min , i_0 , u );m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_min - d_0_N_sqrt_minus ) , Power( u , i_0 - i_min ) ) , Power( m_lazy_substitution , d_0_N_sqrt- i_0 ) );} else {T& m_lazy_action_d = m_lazy_action[d_0_minus];if( m_lazy_action_d == g_e_T ){IntervalAct_Body( i_min , i_0 , t );SetProd( d_0 );} else {IntervalAct_Body( d_0_N_sqrt_minus , i_min , m_lazy_action_d );IntervalAct_Body( i_min , i_0 , m_T( t , m_lazy_action_d ) );IntervalAct_Body( i_0 , d_0_N_sqrt , m_lazy_action_d );m_lazy_action_d = g_e_T;SetProd( d_0 );}}}for( int d = d_0 ; d < d_1 ; d++ ){T& m_lazy_action_d = m_lazy_action[d];if( m_suspended[d] ){SolveSuspension( d , o_U( m_T( t , m_lazy_action_d ) , m_lazy_substitution[d] ) );m_lazy_action_d = g_e_T;} else {m_lazy_action_d = m_T( t , m_lazy_action_d );}}if( i_1 < i_ulim ){// この時d_1 < N_dになる。const int d_1_N_sqrt_plus = d_1_N_sqrt + N_sqrt;U& m_bd = m_b[d_1];if( m_suspended[d_1] ){U& m_lazy_substitution_d = m_lazy_substitution[d_1];const U u = o_U( t , m_lazy_substitution_d );SolveSuspension( d_1 , m_lazy_substitution_d );IntervalSet_Body( i_1 , i_ulim , u );m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_1 - d_1_N_sqrt ) , Power( u , i_ulim - i_1 ) ) , Power( m_lazy_substitution , d_1_N_sqrt_plus -i_ulim ) );} else {T& m_lazy_action_d = m_lazy_action[d_1];if( m_lazy_action_d == g_e_T ){IntervalAct_Body( i_1 , i_ulim , t );SetProd( d_1 );} else {IntervalAct_Body( d_1_N_sqrt , i_1 , m_lazy_action_d );IntervalAct_Body( i_1 , i_ulim , m_T( t , m_lazy_action_d ) );IntervalAct_Body( i_ulim , d_1_N_sqrt_plus , m_lazy_action_d );m_lazy_action_d = g_e_T;SetProd( d_1 );}}}}return;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::Power( const U&u , int exponent ){U answer = g_e_U;U power = u;while( exponent > 0 ){answer = ( exponent & 1 ) == 0 ? answer : m_U( answer , power );power = m_U( power , power );exponent >>= 1;}return answer;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalProd_Body( const int& i_min , const int& i_ulim ) const{U answer = g_e_U;for( int i = i_min ; i < i_ulim ; i++ ){answer = m_U( answer , m_a[i] );}return answer;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::SetProd(const int& d ){U& m_bd = m_b[d] = g_e_U;const int i_min = d * N_sqrt;const int i_ulim = i_min + N_sqrt;for( int i = i_min ; i < i_ulim ; i++ ){m_bd = m_U( m_bd , m_a[i] );}return;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::SolveSuspension( const int& d , const U& u ) { const int i_min = d * N_sqrt; IntervalSet_Body( i_min , i_min + N_sqrt , u ); m_suspended[d] =false; }template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalSet_Body( const int& i_min , const int& i_ulim , const U& u ){for( int i = i_min ; i < i_ulim ; i++ ){m_a[i] = u;}return;}template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalAct_Body( const int& d , T& t ) { const int i_min = d * N_sqrt; IntervalAct_Body( i_min , i_min + N_sqrt , t ); t = g_e_T; }template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalAct_Body( const int& i_min , const int& i_ulim , const T& t ){for( int i = i_min ; i < i_ulim ; i++ ){U& m_ai = m_a[i];m_ai = o_U( t , m_ai );}return;}inline bool m( const bool& b0 , const bool& b1 ) { return b0 && b1; }inline const bool& e() { static const bool b{ true }; return b; }inline const bool& o( const bool& b0 , const bool& b1 ) { return b1; }int main(){UNTIE;CEXPR( ll , bound_N , 1000000000 );CIN_ASSERT( N , 2 , bound_N );CEXPR( int , bound_Q , 200000 );CIN_ASSERT( Q , 1 , bound_Q );map<ll,int> TheAt{};static int type[bound_Q];static ll L[bound_Q];static ll R[bound_Q];FOR( q , 0 , Q ){CIN_ASSERT( type_q , 1 , 4 );type[q] = type_q;if( type_q < 3 ){CIN_ASSERT( L_q , 1 , N );CIN_ASSERT( R_q , L_q + 1 , N );L[q] = L_q;R[q] = R_q - 1;TheAt[L_q-1];TheAt[L_q];TheAt[L_q+1];TheAt[R_q-1];TheAt[R_q];TheAt[R_q+1];} else if( type_q == 3 ){CIN_ASSERT( L_q , 1 , N );CIN_ASSERT( R_q , 1 , N );if( L_q > R_q ){swap( L_q , R_q );}L[q] = L_q;R[q] = R_q - 1;TheAt[L_q-1];TheAt[L_q];TheAt[L_q+1];TheAt[R_q-1];TheAt[R_q];TheAt[R_q+1];} else {CIN_ASSERT( L_q , 1 , N );L[q] = L_q;TheAt[L_q-1];TheAt[L_q];TheAt[L_q+1];}}TheAt[1];TheAt[N];int size = 0;static ll TheAtInv[bound_Q * 4];FOR_ITR( TheAt , itr , end ){TheAtInv[size] = itr->first;itr->second = size++;}CEXPR( int , bound_size , bound_Q * 4 + 2 );constexpr int N_sqrt = SqrtCalculation<bound_size>().m_val;// 座標圧縮された点が右隣と同一連結成分に属すか否かを管理。作用は使わない。static LazySqrtDecomposition<bool,m,e,bool,m,e,m,bound_size,N_sqrt> X{};X.IntervalSet( 0 , bound_size - 1 , false );FOR( q , 0 , Q ){int& type_q = type[q];if( type_q == 1 ){X.IntervalSet( TheAt[L[q]] , TheAt[R[q]] , true );} else if( type_q == 2 ){X.IntervalSet( TheAt[L[q]] , TheAt[R[q]] , false );} else if( type_q == 3 ){COUT( X.IntervalProd( TheAt[L[q]] , TheAt[R[q]] ) ? 1 : 0 );} else {int i = TheAt[L[q]];int d = i / N_sqrt;int d_min = d;int i_min = d_min * N_sqrt;int d_max = d_min + 1;int i_max = i_min + N_sqrt;if( X.IntervalProd( i_min , i - 1 ) ){while( d_min > 0 ? X.IntervalProd( i_min - N_sqrt , i_min - 1 ) : false ){i_min -= N_sqrt;d_min--;}if( d_min > 0 ){while( X.Get( i_min - 1 ) ){i_min--;}}} else {i_min = i;while( X.Get( i_min - 1 ) ){i_min--;}}if( X.IntervalProd( i , i_max - 1 ) ){while( d_max < X.N_d ? X.IntervalProd( i_max , i_max + N_sqrt - 1 ) : false ){i_max += N_sqrt;d_max++;}if( d_max < X.N_d ){while( X.Get( i_max ) ){i_max++;}}} else {i_max = i;while( X.Get( i_max ) ){i_max++;}}COUT( ( i_max < size ? TheAtInv[i_max] : N ) - TheAtInv[i_min] + 1 );}}QUIT;}