#868128 (C++17) No.2292 Interval Union Find

提出ソース

結果

問題	No.2292 Interval Union Find
ユーザー	👑 p-adic
提出日時	2023-05-12 15:12:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	922 ms / 5,000 ms
コード長	18,465 bytes
コンパイル時間	3,773 ms
コンパイル使用メモリ	246,720 KB
実行使用メモリ	64,384 KB
最終ジャッジ日時	2024-05-06 07:30:33
合計ジャッジ時間	36,301 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	471 ms 15,104 KB
testcase_05	AC	415 ms 16,128 KB
testcase_06	AC	435 ms 14,976 KB
testcase_07	AC	399 ms 15,232 KB
testcase_08	AC	863 ms 46,592 KB
testcase_09	AC	871 ms 46,592 KB
testcase_10	AC	820 ms 45,952 KB
testcase_11	AC	849 ms 45,440 KB
testcase_12	AC	836 ms 46,848 KB
testcase_13	AC	792 ms 39,808 KB
testcase_14	AC	885 ms 43,264 KB
testcase_15	AC	888 ms 44,544 KB
testcase_16	AC	875 ms 42,368 KB
testcase_17	AC	922 ms 46,464 KB
testcase_18	AC	404 ms 50,176 KB
testcase_19	AC	756 ms 64,384 KB
testcase_20	AC	734 ms 64,384 KB
testcase_21	AC	678 ms 55,552 KB
testcase_22	AC	679 ms 55,552 KB
testcase_23	AC	678 ms 55,680 KB
testcase_24	AC	667 ms 55,808 KB
testcase_25	AC	673 ms 55,680 KB
testcase_26	AC	673 ms 55,424 KB
testcase_27	AC	681 ms 55,680 KB
testcase_28	AC	674 ms 55,552 KB
testcase_29	AC	678 ms 55,552 KB
testcase_30	AC	699 ms 55,552 KB
testcase_31	AC	678 ms 55,424 KB
testcase_32	AC	671 ms 55,680 KB
testcase_33	AC	679 ms 55,552 KB
testcase_34	AC	676 ms 55,552 KB
testcase_35	AC	683 ms 55,552 KB
testcase_36	AC	687 ms 55,808 KB
testcase_37	AC	703 ms 55,552 KB
testcase_38	AC	690 ms 55,680 KB
testcase_39	AC	676 ms 55,552 KB
testcase_40	AC	672 ms 55,680 KB
testcase_41	AC	80 ms 8,192 KB
testcase_42	AC	83 ms 8,192 KB
testcase_43	AC	94 ms 8,064 KB
testcase_44	AC	160 ms 8,192 KB
testcase_45	AC	181 ms 8,320 KB
testcase_46	AC	185 ms 8,192 KB
testcase_47	AC	304 ms 8,448 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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+log_2 N,N^{1/2}))（Uのモノイド性を使う。区間代入更新を使っていなければlog_2 Nの寄与はO(1)になる）

// 一点更新O(N^{1/2})
// 区間代入更新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 SolveSuspendedSubstitution( 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 SolveSuspendedAction( const int& d );
  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になる。
    const int d_0_minus = d_0 - 1;
    answer = m_suspended[d_0_minus] ? Power( m_lazy_substitution[d_0_minus] , i_0 - i_min ) : o_U( m_lazy_action[d_0_minus] , IntervalProd_Body( i_min , i_0 ) );
    
  }
  
  for( int d = d_0 ; d < d_1 ; d++ ){

    answer = m_U( answer , 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( const int& 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 ){

      SolveSuspendedSubstitution( d , m_lazy_substitution_d );
      m_ai = u;
      m_b[d] = m_U( m_U( Power( m_lazy_substitution_d , i - i_min ) , u ) , Power( m_lazy_substitution_d , i_ulim - ( i + 1 ) ) );

    }
      
  } else {

    SolveSuspendedAction( d );

    if( m_ai != u ){

      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];
    bool& 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_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 {

      SolveSuspendedAction( d_0_minus );
      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( i_0 , d_0_N_sqrt ) );
      
    }
    
  }

  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];
    bool& 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_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 {

      SolveSuspendedAction( d_1 );
      IntervalSet_Body( i_1 , i_ulim , u );
      m_bd = m_U( m_U( IntervalProd_Body( d_1_N_sqrt , i_1 ) , Power( u , i_ulim - i_1 ) ) , IntervalProd_Body( i_ulim , d_1_N_sqrt_plus ) );
      
    }
    
  }
  
  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;
      bool& m_suspended_d = m_suspended[d_0_minus];

      if( m_suspended_d ){

	U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];
	U& m_bd = m_b[d_0_minus];
	const U u = o_U( t , m_lazy_substitution_d );
	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 = false;
	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 );

	} 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_minus );
      
      }

    }
  
    for( int d = d_0 ; d < d_1 ; d++ ){

      U& m_bd = m_b[d];
      m_bd = o_U( t , m_bd );

      if( m_suspended[d] ){

	U& m_lazy_substitution_d = m_lazy_substitution[d];
	m_lazy_substitution_d = o_U( t , m_lazy_substitution_d );

      } else {
      
	T& m_lazy_action_d = m_lazy_action[d];
	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;
      bool& m_suspended_d = m_suspended[d_1];

      if( m_suspended_d ){

	U& m_lazy_substitution_d = m_lazy_substitution[d_1];
	U& m_bd = m_b[d_1];
	const U u = o_U( t , m_lazy_substitution_d );
	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 = false;
	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;

  if( u != 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>::SolveSuspendedSubstitution( 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;
  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_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>::SolveSuspendedAction( const int& d )
{

  T& m_lazy_action_d = m_lazy_action[d];

  if( m_lazy_action_d != g_e_T ){

    const int i_min = d * N_sqrt;
    const int i_ulim = i_min + N_sqrt;
    IntervalAct_Body( i_min , i_ulim , m_lazy_action_d );
    U& m_bd = m_b[d];
    m_bd = o_U( m_lazy_action_d , m_bd );
    m_lazy_action_d = g_e_T;
 
  }

  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& 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[R_q-1];
      TheAt[R_q];
    } 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];
      TheAt[R_q - 1];
    } else {
      CIN_ASSERT( L_q , 1 , N );
      L[q] = L_q;
      TheAt[L_q];
    }
  }
  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;
}

yukicoder

結果

テストケース

ソースコード