#799718 (C++17) No.2072 Anatomy

提出ソース
結果

問題	No.2072 Anatomy
ユーザー	👑 p-adic
提出日時	2022-09-22 10:42:54
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	93 ms / 2,000 ms
コード長	56,606 bytes
コンパイル時間	2,100 ms
コンパイル使用メモリ	207,096 KB
実行使用メモリ	38,872 KB
最終ジャッジ日時	2023-08-23 20:27:25
合計ジャッジ時間	6,081 ms
ジャッジサーバーID （参考情報）	judge12 / judge13
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	76 ms 32,604 KB
testcase_09	AC	76 ms 34,964 KB
testcase_10	AC	65 ms 25,012 KB
testcase_11	AC	78 ms 32,464 KB
testcase_12	AC	53 ms 22,552 KB
testcase_13	AC	93 ms 36,760 KB
testcase_14	AC	45 ms 21,320 KB
testcase_15	AC	46 ms 23,744 KB
testcase_16	AC	89 ms 37,436 KB
testcase_17	AC	77 ms 35,756 KB
testcase_18	AC	37 ms 21,252 KB
testcase_19	AC	93 ms 37,876 KB
testcase_20	AC	92 ms 38,140 KB
testcase_21	AC	80 ms 38,176 KB
testcase_22	AC	88 ms 38,872 KB
testcase_23	AC	84 ms 38,152 KB
testcase_24	AC	81 ms 38,372 KB
testcase_25	AC	89 ms 38,600 KB
testcase_26	AC	1 ms 4,376 KB
testcase_27	AC	82 ms 37,752 KB
testcase_28	AC	56 ms 37,624 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #define _GLIBCXX_DEBUG 
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decltype( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( decltype( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
#define TMP template
#define TYP typename
#define INL inline
#define RET return
#define CST const
#define NEX noexcept
#define OPR operator
#define PUB public
#define PRI private
TMP <TYP T> INL T Absolute( CST T& a ){ RET a > 0 ? a : - a; }
#define INT_REF CST int
#define CONST_INT_REF CST int
#define CONST_UINT_REF CST uint
// #define INT_REF int&
// #define CONST_INT_REF CST int&
// #define CONST_UINT_REF CST uint&
// 以下、自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
TMP <TYP T> class LinkedVector;
TMP <TYP T> class IteratorOfLinkedVector;
TMP <TYP T> class ConstIteratorOfLinkedVector;
TMP <TYP T> class UnionFindForest;
TMP <TYP T>
class EntryOfLinkedVector
{
friend class LinkedVector<T>;
friend class IteratorOfLinkedVector<T>;
friend class ConstIteratorOfLinkedVector<T>;
TMP <TYP U> friend class UnionFindForest;

PRI:
T m_t;
uint m_prev_entry;
uint m_next_entry;
PRI:
INL EntryOfLinkedVector();
INL EntryOfLinkedVector( CONST_UINT_REF prev_entry , CONST_UINT_REF next_entry );
PUB:
// vectorのreserveに必要。
INL EntryOfLinkedVector( EntryOfLinkedVector<T>&& e );
};
TMP <TYP T> INL EntryOfLinkedVector<T>::EntryOfLinkedVector() : m_t() , m_prev_entry( 0 ) , m_next_entry( 0 ) {}
TMP <TYP T> INL EntryOfLinkedVector<T>::EntryOfLinkedVector( CONST_UINT_REF prev_entry , CONST_UINT_REF next_entry ) : m_t() , m_prev_entry( prev_entry ) , m_next_entry( next_entry ) {}
TMP <TYP T> INL EntryOfLinkedVector<T>::EntryOfLinkedVector( EntryOfLinkedVector<T>&& e ) : m_t( move( e.m_t ) ) , m_prev_entry( move( e.m_prev_entry ) ) , m_next_entry( move( e.m_next_entry ) ) {}
TMP <TYP T> class EntryOfLinkedVector;
TMP <TYP T> class ConstIteratorOfLinkedVector;
TMP <TYP T> class LinkedVector;
TMP <TYP T>
class IteratorOfLinkedVector
{
friend ConstIteratorOfLinkedVector<T>;
friend LinkedVector<T>;
PRI:
LinkedVector<T>* m_p;
uint m_i;

PUB:
INL IteratorOfLinkedVector( LinkedVector<T>* const& p , CONST_UINT_REF i ) NEX;
INL IteratorOfLinkedVector( CST IteratorOfLinkedVector<T>& itr ) NEX;
INL T& OPR*() CST;
INL T* OPR->() CST;
IteratorOfLinkedVector<T>& OPR=( CST IteratorOfLinkedVector<T>& itr ) NEX;
INL void OPR++( int );
INL void OPR--( int );
INL CST LinkedVector<T>& GetLinkedVector() CST NEX;
INL LinkedVector<T>& RefLinkedVector() NEX;
INL CONST_UINT_REF GetIndex() CST NEX;
INL CONST_UINT_REF RefIndex() NEX;
};
TMP <TYP T>
class ConstIteratorOfLinkedVector
{
friend LinkedVector<T>;
PRI:
CST LinkedVector<T>* m_p;
uint m_i;

PUB:
INL ConstIteratorOfLinkedVector( CST LinkedVector<T>* const& p , CONST_UINT_REF i ) NEX;
INL ConstIteratorOfLinkedVector( CST ConstIteratorOfLinkedVector<T>& itr ) NEX;
INL ConstIteratorOfLinkedVector( CST IteratorOfLinkedVector<T>& itr ) NEX;
INL CST T& OPR*() CST;
INL CST T* OPR->() CST;
ConstIteratorOfLinkedVector<T>& OPR=( CST ConstIteratorOfLinkedVector<T>& itr ) NEX;
ConstIteratorOfLinkedVector<T>& OPR=( CST IteratorOfLinkedVector<T>& itr ) NEX;
INL void OPR++( int );
INL void OPR--( int );
INL CST LinkedVector<T>& GetLinkedVector() CST NEX;
INL CONST_UINT_REF GetIndex() CST NEX;
INL CONST_UINT_REF RefIndex() NEX;

static INL bool Equal( CST IteratorOfLinkedVector<T>& , CST IteratorOfLinkedVector<T>& ) NEX;
static INL bool Equal( CST ConstIteratorOfLinkedVector<T>& , CST IteratorOfLinkedVector<T>& ) NEX;
static INL bool Equal( CST IteratorOfLinkedVector<T>& , CST ConstIteratorOfLinkedVector<T>& ) NEX;
static INL bool Equal( CST ConstIteratorOfLinkedVector<T>& , CST ConstIteratorOfLinkedVector<T>& ) NEX;
};
TMP <TYP T> INL bool OPR==( CST IteratorOfLinkedVector<T>& , CST IteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IteratorOfLinkedVector<T>& , CST IteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfLinkedVector<T>& , CST IteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfLinkedVector<T>& , CST IteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST IteratorOfLinkedVector<T>& , CST ConstIteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IteratorOfLinkedVector<T>& , CST ConstIteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfLinkedVector<T>& , CST ConstIteratorOfLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfLinkedVector<T>& , CST ConstIteratorOfLinkedVector<T>& ) NEX;
// IteratorOfLinkedVector
TMP <TYP T> INL IteratorOfLinkedVector<T>::IteratorOfLinkedVector( LinkedVector<T>* const& p , CONST_UINT_REF i ) NEX : m_p( p ) , m_i( i ) {}
TMP <TYP T> INL IteratorOfLinkedVector<T>::IteratorOfLinkedVector( CST IteratorOfLinkedVector<T>& itr ) NEX : m_p( itr.m_p ) , m_i( itr.m_i ) {}
TMP <TYP T> INL T& IteratorOfLinkedVector<T>::OPR*() CST { RET ( *m_p )[m_i]; }
TMP <TYP T> INL T* IteratorOfLinkedVector<T>::OPR->() CST { RET &( ( *m_p )[m_i] ); }
TMP <TYP T> INL IteratorOfLinkedVector<T>& IteratorOfLinkedVector<T>::OPR=( CST IteratorOfLinkedVector<T>& itr ) NEX { m_p = itr.m_p; m_i = itr.m_i; RET *this; }
TMP <TYP T> INL void IteratorOfLinkedVector<T>::OPR++( int ) { m_i = m_p->m_entry[m_i].m_next_entry; }
TMP <TYP T> INL void IteratorOfLinkedVector<T>::OPR--( int ) { m_i = m_p->m_entry[m_i].m_prev_entry; }
TMP <TYP T> INL CST LinkedVector<T>& IteratorOfLinkedVector<T>::GetLinkedVector() CST NEX { RET *m_p; }
TMP <TYP T> INL LinkedVector<T>& IteratorOfLinkedVector<T>::RefLinkedVector() NEX { RET *m_p; }
TMP <TYP T> INL CONST_UINT_REF IteratorOfLinkedVector<T>::GetIndex() CST NEX { RET m_i; }
TMP <TYP T> INL CONST_UINT_REF IteratorOfLinkedVector<T>::RefIndex() NEX { RET m_i; }
// ConstIteratorOfLinkedVector
TMP <TYP T> INL ConstIteratorOfLinkedVector<T>::ConstIteratorOfLinkedVector( CST LinkedVector<T>* const& p , CONST_UINT_REF i ) NEX : m_p( p ) , m_i( i ) {}
TMP <TYP T> INL ConstIteratorOfLinkedVector<T>::ConstIteratorOfLinkedVector( CST ConstIteratorOfLinkedVector<T>& itr ) NEX : m_p( itr.m_p ) , m_i( itr.m_i ) {}
TMP <TYP T> INL ConstIteratorOfLinkedVector<T>::ConstIteratorOfLinkedVector( CST IteratorOfLinkedVector<T>& itr ) NEX : m_p( itr.m_p ) , m_i( itr.m_i ) {}
TMP <TYP T> INL CST T& ConstIteratorOfLinkedVector<T>::OPR*() CST { RET ( *m_p )[m_i]; }
TMP <TYP T> INL CST T* ConstIteratorOfLinkedVector<T>::OPR->() CST { RET &( ( *m_p )[m_i] ); }
TMP <TYP T>
ConstIteratorOfLinkedVector<T>& ConstIteratorOfLinkedVector<T>::OPR=( CST ConstIteratorOfLinkedVector<T>& itr ) NEX { m_p = itr.m_p; m_i = itr.m_i; RET *this; }
TMP <TYP T>
ConstIteratorOfLinkedVector<T>& ConstIteratorOfLinkedVector<T>::OPR=( CST IteratorOfLinkedVector<T>& itr ) NEX { m_p = itr.m_p; m_i = itr.m_i; RET *this; }
TMP <TYP T> INL void ConstIteratorOfLinkedVector<T>::OPR++( int ) { m_i = m_p->m_entry[m_i].m_next_entry; }
TMP <TYP T> INL void ConstIteratorOfLinkedVector<T>::OPR--( int ) { m_i = m_p->m_entry[m_i].m_prev_entry; }
TMP <TYP T> INL CST LinkedVector<T>& ConstIteratorOfLinkedVector<T>::GetLinkedVector() CST NEX { RET *m_p; }
TMP <TYP T> INL CONST_UINT_REF ConstIteratorOfLinkedVector<T>::GetIndex() CST NEX { RET m_i; }
TMP <TYP T> INL CONST_UINT_REF ConstIteratorOfLinkedVector<T>::RefIndex() NEX { RET m_i; }
TMP <TYP T> INL bool ConstIteratorOfLinkedVector<T>::Equal( CST IteratorOfLinkedVector<T>& itr0 , CST IteratorOfLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool ConstIteratorOfLinkedVector<T>::Equal( CST ConstIteratorOfLinkedVector<T>& itr0 , CST IteratorOfLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool ConstIteratorOfLinkedVector<T>::Equal( CST IteratorOfLinkedVector<T>& itr0 , CST ConstIteratorOfLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool ConstIteratorOfLinkedVector<T>::Equal( CST ConstIteratorOfLinkedVector<T>& itr0 , CST ConstIteratorOfLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool OPR==( CST IteratorOfLinkedVector<T>& itr0 , CST IteratorOfLinkedVector<T>& itr1 ) NEX { RET ConstIteratorOfLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IteratorOfLinkedVector<T>& itr0 , CST IteratorOfLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfLinkedVector<T>& itr0 , CST IteratorOfLinkedVector<T>& itr1 ) NEX { RET ConstIteratorOfLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfLinkedVector<T>& itr0 , CST IteratorOfLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST IteratorOfLinkedVector<T>& itr0 , CST ConstIteratorOfLinkedVector<T>& itr1 ) NEX { RET ConstIteratorOfLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IteratorOfLinkedVector<T>& itr0 , CST ConstIteratorOfLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfLinkedVector<T>& itr0 , CST ConstIteratorOfLinkedVector<T>& itr1 ) NEX { RET ConstIteratorOfLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfLinkedVector<T>& itr0 , CST ConstIteratorOfLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> class IteratorOfLinkedVector;
TMP <TYP T> class ConstIteratorOfLinkedVector;
TMP <TYP T>
class LinkedVector
{
friend IteratorOfLinkedVector<T>;
friend ConstIteratorOfLinkedVector<T>;
protected:
vector<EntryOfLinkedVector<T> > m_entry;
uint m_front_linked_entry;
uint m_back_linked_entry;
uint m_size_of_vector;
uint m_size_of_link;
PUB:
INL LinkedVector();
// 要素やそのメンバへのポインタをメンバに持ちうるクラスに対しては
// vectorのcapacityを超える際のコピーでポインタの参照先が無効になってしまうので
// 予め最大要素数を設定する。
INL LinkedVector( CONST_UINT_REF max_size );
// vector上でi番目の要素を返す。
INL CST T& OPR[]( CONST_UINT_REF i ) CST;
INL T& OPR[]( CONST_UINT_REF i );
// link上でi番目の要素の座標を返す。
uint GetLinkedEntry( CONST_UINT_REF i ) CST;
INL CONST_UINT_REF GetFrontLinkedEntryIndex() CST NEX;
INL CONST_UINT_REF GetBackLinkedEntryIndex() CST NEX;
INL CONST_UINT_REF GetSizeOfVector() CST NEX;
INL CONST_UINT_REF GetSizeOfLink() CST NEX;
INL bool EmptyVector() CST NEX;
INL bool EmptyLink() CST NEX;
INL void push_back();
TMP <TYP U> void push_back( CST U& u );
TMP <TYP U , TYP... ARGS> INL void push_back( CST U& u , CST ARGS&... args );
INL void SetPreviousLink( CONST_UINT_REF i , CONST_UINT_REF j );
INL void SetNexttLink( CONST_UINT_REF i , CONST_UINT_REF j );
INL CONST_UINT_REF GetPreviousLinkIndex( CONST_UINT_REF i ) CST;
INL CONST_UINT_REF GetNexttLinkIndex( CONST_UINT_REF i ) CST;
// vector上でi番目の要素がlink上にある場合のみサポート
CONST_UINT_REF DeLink( CONST_UINT_REF i );
// vector上でi番目の要素がlink上にない場合のみサポート
void ReLink( CONST_UINT_REF i );
using iterator = IteratorOfLinkedVector<T>;
using const_iterator = ConstIteratorOfLinkedVector<T>;
// *thisがconstである場合に確実にconst_iterator返しをするために、iterator返しは非constにする必要がある。
INL iterator GetIterator( CONST_UINT_REF i ) NEX;
INL const_iterator GetIterator( CONST_UINT_REF i ) CST NEX;
INL iterator begin() NEX;
INL const_iterator begin() CST NEX;
INL iterator end() NEX;
INL const_iterator end() CST NEX;
// itrの指す要素がlink上にある場合のみサポート
iterator erase( iterator& itr );
protected:
INL EntryOfLinkedVector<T>& push_back_Body_0();
INL void push_back_Body_1( EntryOfLinkedVector<T>& e );

};
TMP <TYP T> INL LinkedVector<T>::LinkedVector() : m_entry( 1 ) , m_front_linked_entry( 0 ) , m_back_linked_entry( 0 ) , m_size_of_vector( 0 ) , m_size_of_link( 0 ) {}
TMP <TYP T>
LinkedVector<T>::LinkedVector( CONST_UINT_REF max_size ) : m_entry() , m_front_linked_entry( 0 ) , m_back_linked_entry( 0 ) , m_size_of_vector( 0 ) , m_size_of_link( 0 )
{
m_entry.shrink_to_fit();
CST uint capacity = m_entry.capacity();
m_entry.reserve( max_size );
// 一旦メモリの再確保を生じさせる。
for( uint i = 0 ; i <= capacity ; i++ ){
m_entry.push_back( EntryOfLinkedVector<T>() );
}
for( uint i = 0 ; i < capacity ; i++ ){
m_entry.pop_back();
}

}
TMP <TYP T> INL CST T& LinkedVector<T>::OPR[]( CONST_UINT_REF i ) CST { RET m_entry[i].m_t; }
TMP <TYP T> INL T& LinkedVector<T>::OPR[]( CONST_UINT_REF i ) { RET m_entry[i].m_t; }
TMP <TYP T>
uint LinkedVector<T>::GetLinkedEntry( CONST_UINT_REF i ) const
{
uint linked_entry = m_front_linked_entry;
for( uint j = 0 ; j < i ; j++ ){
linked_entry = m_entry[linked_entry].m_next_entry;
}
RET linked_entry;

}
TMP <TYP T> INL CONST_UINT_REF LinkedVector<T>::GetFrontLinkedEntryIndex() CST NEX { RET m_front_linked_entry; }
TMP <TYP T> INL CONST_UINT_REF LinkedVector<T>::GetBackLinkedEntryIndex() CST NEX { RET m_back_linked_entry; }
TMP <TYP T> INL CONST_UINT_REF LinkedVector<T>::GetSizeOfVector() CST NEX { RET m_size_of_vector; }
TMP <TYP T> INL CONST_UINT_REF LinkedVector<T>::GetSizeOfLink() CST NEX { RET m_size_of_link; }
TMP <TYP T> INL bool LinkedVector<T>::EmptyVector() CST NEX { RET m_size_of_vector == 0; }
TMP <TYP T> INL bool LinkedVector<T>::EmptyLink() CST NEX { RET m_size_of_link == 0; }
TMP <TYP T> INL void LinkedVector<T>::push_back() {}
TMP <TYP T> TMP <TYP U>
void LinkedVector<T>::push_back( CST U& u )
{
EntryOfLinkedVector<T>& e = push_back_Body_0();
e.m_t = u;
push_back_Body_1( e );
RET;

}
TMP <TYP T> TMP <TYP U , TYP... ARGS> INL void LinkedVector<T>::push_back( CST U& u , CST ARGS&... args ) { push_back( u ); push_back( args... ); }
TMP <TYP T> INL EntryOfLinkedVector<T>& LinkedVector<T>::push_back_Body_0() { m_entry.push_back( EntryOfLinkedVector<T>( m_size_of_vector , m_front_linked_entry ) ); RET m_entry[m_size_of_vector]; }
TMP <TYP T> INL void LinkedVector<T>::push_back_Body_1( EntryOfLinkedVector<T>& e ) { e.m_next_entry = m_size_of_vector + 1; m_entry[m_front_linked_entry].m_prev_entry = m_size_of_vector + 1; m_back_linked_entry = m_size_of_vector; m_size_of_vector++; m_size_of_link++; }
TMP <TYP T> INL void LinkedVector<T>::SetPreviousLink( CONST_UINT_REF i , CONST_UINT_REF j ) { m_entry[i].m_prev_entry = j; }
TMP <TYP T> INL void LinkedVector<T>::SetNexttLink( CONST_UINT_REF i , CONST_UINT_REF j ) { m_entry[i].m_next_entry = j; }
TMP <TYP T> INL CONST_UINT_REF LinkedVector<T>::GetPreviousLinkIndex( CONST_UINT_REF i ) CST { RET m_entry[i].m_prev_entry; }
TMP <TYP T> INL CONST_UINT_REF LinkedVector<T>::GetNexttLinkIndex( CONST_UINT_REF i ) CST { RET m_entry[i].m_next_entry; }
TMP <TYP T>
CONST_UINT_REF LinkedVector<T>::DeLink( CONST_UINT_REF i )
{
CST EntryOfLinkedVector<T>& e = m_entry[i];
m_entry[e.m_prev_entry].m_next_entry = e.m_next_entry;
m_entry[e.m_next_entry].m_prev_entry = e.m_prev_entry;
if( m_front_linked_entry == i ){
m_front_linked_entry = e.m_next_entry;
}
if( m_back_linked_entry == i ){
m_back_linked_entry = e.m_prev_entry;
}
m_size_of_link--;
RET e.m_next_entry;
}
TMP <TYP T>
void LinkedVector<T>::ReLink( CONST_UINT_REF i )
{
EntryOfLinkedVector<T>& current_entry = m_entry[i];
if( m_size_of_link == 0 ){
EntryOfLinkedVector<T>& end_entry = m_entry[m_size_of_vector];
end_entry.m_prev_entry = end_entry.m_next_entry = i;
current_entry.m_prev_entry = current_entry.m_next_entry = m_size_of_vector;
m_front_linked_entry = m_back_linked_entry = i;
} else {
uint prev;
if( m_front_linked_entry > i ){
m_front_linked_entry = i;
prev = m_size_of_vector;
} else {
prev = m_front_linked_entry;
}
if( m_back_linked_entry < i ){
m_back_linked_entry = i;

}

prev = m_entry[prev].m_next_entry;

while( prev < i ){
prev = m_entry[prev].m_next_entry;
}
CST uint next = prev;
EntryOfLinkedVector<T>& next_entry = m_entry[next];
prev = next_entry.m_prev_entry;
EntryOfLinkedVector<T>& prev_entry = m_entry[prev];
prev_entry.m_next_entry = i;
current_entry.m_prev_entry = prev;
current_entry.m_next_entry = next;
next_entry.m_prev_entry = i;
}

m_size_of_link++;
RET;

}
TMP <TYP T> INL TYP LinkedVector<T>::iterator LinkedVector<T>::GetIterator( CONST_UINT_REF i ) NEX { RET TYP LinkedVector<T>::iterator( this , i ); }
TMP <TYP T> INL TYP LinkedVector<T>::const_iterator LinkedVector<T>::GetIterator( CONST_UINT_REF i ) CST NEX { RET TYP LinkedVector<T>::const_iterator( this , i ); }
TMP <TYP T> INL TYP LinkedVector<T>::iterator LinkedVector<T>::begin() NEX { RET TYP LinkedVector<T>::iterator( this , m_front_linked_entry ); }
TMP <TYP T> INL TYP LinkedVector<T>::const_iterator LinkedVector<T>::begin() CST NEX { RET TYP LinkedVector<T>::const_iterator( this , m_front_linked_entry ); }
TMP <TYP T> INL TYP LinkedVector<T>::iterator LinkedVector<T>::end() NEX { RET TYP LinkedVector<T>::iterator( this , m_size_of_vector ); }
TMP <TYP T> INL TYP LinkedVector<T>::const_iterator LinkedVector<T>::end() CST NEX { RET TYP LinkedVector<T>::const_iterator( this , m_size_of_vector ); }
TMP <TYP T> TYP LinkedVector<T>::iterator LinkedVector<T>::erase( TYP LinkedVector<T>::iterator& itr ) { RET TYP LinkedVector<T>::iterator( this , DeLink( itr.m_i ) ); }
TMP <TYP T> class IteratorOfVLTree;
TMP <TYP T> class ConstIteratorOfVLTree;
TMP <TYP T> class VLSubTree;
TMP <TYP T> class EntryOfUnionFindForest;
TMP <TYP T>
class EntryOfVLTree
{
friend IteratorOfVLTree<T>;
friend ConstIteratorOfVLTree<T>;
friend VLSubTree<T>;
friend EntryOfUnionFindForest<T>;
PRI:
T m_t;
EntryOfVLTree<T>* m_left_branch;
EntryOfVLTree<T>* m_right_branch;
EntryOfVLTree<T>* m_leftmost_node;
EntryOfVLTree<T>* m_rightmost_node;

PRI:
INL EntryOfVLTree();
TMP <TYP Arg> INL EntryOfVLTree( CST Arg& );
TMP <TYP Arg> INL EntryOfVLTree( CST Arg& , EntryOfVLTree<T>* const& , EntryOfVLTree<T>* const& );
INL EntryOfVLTree( CST EntryOfVLTree<T>& );
EntryOfVLTree<T>& OPR=( CST EntryOfVLTree<T>& );
};
TMP <TYP T> INL EntryOfVLTree<T>::EntryOfVLTree() : m_t() , m_left_branch( this ) , m_right_branch( this ) , m_leftmost_node( this ) , m_rightmost_node( this ) {}
TMP <TYP T> TMP <TYP Arg> INL EntryOfVLTree<T>::EntryOfVLTree( CST Arg& t ) : EntryOfVLTree( t , this , this ) {}
TMP <TYP T> TMP <TYP Arg> INL EntryOfVLTree<T>::EntryOfVLTree( CST Arg& t , EntryOfVLTree<T>* const& left_branch , EntryOfVLTree<T>* const& right_branch ) : m_t( t ) , m_left_branch( left_branch ) , m_right_branch( right_branch ) , m_leftmost_node( this ) , m_rightmost_node( this ) {}
TMP <TYP T> INL EntryOfVLTree<T>::EntryOfVLTree( CST EntryOfVLTree<T>& e ) : m_t( e.m_t ) , m_left_branch( e.m_left_branch == &e ? this : e.m_left_branch ) , m_right_branch( e.m_right_branch == &e ? this : e.m_right_branch ) , m_leftmost_node( this ) , m_rightmost_node( this ) { if( e.m_leftmost_node != &e ){ m_leftmost_node = e.m_leftmost_node; m_rightmost_node = e.m_rightmost_node; } }
TMP <TYP T> EntryOfVLTree<T>& EntryOfVLTree<T>::OPR=( CST EntryOfVLTree<T>& e )
{
m_t = e.m_t;
m_left_branch = ( e.m_left_branch == &e ? this : e.m_left_branch );
m_right_branch = ( e.m_right_branch == &e ? this : e.m_right_branch );
if( e.m_leftmost_node == &e ){
m_leftmost_node = m_rightmost_node = this;
} else {
m_leftmost_node = e.m_leftmost_node;
m_rightmost_node = e.m_rightmost_node;
}
RET *this;
}

TMP <TYP T> class EntryOfVLTree;
TMP <TYP T> class ConstIteratorOfVLTree;
TMP <TYP T> class VLSubTree;
TMP <TYP T> class EntryOfVLArray;
TMP <TYP T>
class IteratorOfVLTree
{
friend ConstIteratorOfVLTree<T>;
friend VLSubTree<T>;
friend EntryOfVLArray<IteratorOfVLTree<T> >;
PRI:
EntryOfVLTree<T>* m_p;
PRI:
// SequentialIteratorOVLTree経由でのみ呼び出し可能。
INL IteratorOfVLTree() NEX;
PUB:
INL IteratorOfVLTree( EntryOfVLTree<T>* const& ) NEX;
INL IteratorOfVLTree( CST IteratorOfVLTree<T>& ) NEX;
// 非メンバ関数のAccess用
// INL T& Access_Body( CST char* CST , CONST_INT_REF , CST char* CST , CST string& ) CST;
INL T& OPR*() CST;
INL T* OPR->() CST;
IteratorOfVLTree<T>& OPR=( CST IteratorOfVLTree<T>& ) NEX;
// 通常と異なり自身への参照を渡す。
IteratorOfVLTree<T>& OPR++( int ) NEX;
IteratorOfVLTree<T>& OPR--( int ) NEX;
// 引数が0の時は何もしない。正の時はm_leftmost_nodeに進んでインクリメント、負の時はm_rightmost_nodeに進んでディクリメント。
IteratorOfVLTree<T>& OPR[]( CONST_INT_REF );
IteratorOfVLTree<T>& Shift() NEX;
TMP <TYP... Args> IteratorOfVLTree<T>& Shift( CONST_INT_REF , CST Args&... );

INL bool IsLeaf() CST NEX;
INL bool IsLeftMost() CST NEX;
INL bool IsRightMost() CST NEX;
INL bool IsValid() CST NEX;
};
TMP <TYP T>
class ConstIteratorOfVLTree
{
friend VLSubTree<T>;
friend EntryOfVLArray<ConstIteratorOfVLTree<T> >;
PRI:
CST EntryOfVLTree<T>* m_p;
PRI:
// SequentialConstIteratorOVLTree経由でのみ呼び出し可能。
INL ConstIteratorOfVLTree() NEX;

PUB:
INL ConstIteratorOfVLTree( CST EntryOfVLTree<T>* const& ) NEX;
INL ConstIteratorOfVLTree( CST ConstIteratorOfVLTree<T>& ) NEX;
INL ConstIteratorOfVLTree( CST IteratorOfVLTree<T>& ) NEX;
// 非メンバ関数のAccess用
// INL CST T& Access_Body( CST char* CST , CONST_INT_REF , CST char* CST , CST string& ) CST;
INL CST T& OPR*() CST;
INL CST T* OPR->() CST;
ConstIteratorOfVLTree<T>& OPR=( CST ConstIteratorOfVLTree<T>& ) NEX;
ConstIteratorOfVLTree<T>& OPR=( CST IteratorOfVLTree<T>& ) NEX;
// 通常と異なり自身への参照を渡す。
ConstIteratorOfVLTree<T>& OPR++( int ) NEX;
ConstIteratorOfVLTree<T>& OPR--( int ) NEX;
// 引数が0の時は何もしない。正の時はm_leftmost_nodeに進んでインクリメント、負の時はm_rightmost_nodeに進んでディクリメント。
ConstIteratorOfVLTree<T>& OPR[]( CONST_INT_REF );
ConstIteratorOfVLTree<T>& Shift() NEX;
TMP <TYP... Args> ConstIteratorOfVLTree<T>& Shift( CONST_INT_REF , CST Args&... );
INL bool IsLeaf() CST NEX;
INL bool IsLeftMost() CST NEX;
INL bool IsRightMost() CST NEX;
INL bool IsValid() CST NEX;
static INL bool Equal( CST IteratorOfVLTree<T>& , CST IteratorOfVLTree<T>& ) NEX;
static INL bool Equal( CST ConstIteratorOfVLTree<T>& , CST IteratorOfVLTree<T>& ) NEX;
static INL bool Equal( CST IteratorOfVLTree<T>& , CST ConstIteratorOfVLTree<T>& ) NEX;
static INL bool Equal( CST ConstIteratorOfVLTree<T>& , CST ConstIteratorOfVLTree<T>& ) NEX;
};
TMP <TYP T> INL bool OPR==( CST IteratorOfVLTree<T>& , CST IteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IteratorOfVLTree<T>& , CST IteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfVLTree<T>& , CST IteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfVLTree<T>& , CST IteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST IteratorOfVLTree<T>& , CST ConstIteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IteratorOfVLTree<T>& , CST ConstIteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfVLTree<T>& , CST ConstIteratorOfVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfVLTree<T>& , CST ConstIteratorOfVLTree<T>& ) NEX;
// IteratorOfVLTree
TMP <TYP T> INL IteratorOfVLTree<T>::IteratorOfVLTree() NEX : m_p( nullptr ) {}
TMP <TYP T> INL IteratorOfVLTree<T>::IteratorOfVLTree( EntryOfVLTree<T>* const& p ) NEX : m_p( p ) {}
TMP <TYP T> INL IteratorOfVLTree<T>::IteratorOfVLTree( CST IteratorOfVLTree<T>& itr ) NEX : m_p( itr.m_p ) {}
TMP <TYP T> INL T& IteratorOfVLTree<T>::OPR*() CST { RET ( *m_p ).m_t; }
TMP <TYP T> INL T* IteratorOfVLTree<T>::OPR->() CST { RET &( *( *this ) ); }
TMP <TYP T>
IteratorOfVLTree<T>& IteratorOfVLTree<T>::OPR=( CST IteratorOfVLTree<T>& itr ) NEX
{
m_p = itr.m_p;
RET *this;

}
TMP <TYP T>
IteratorOfVLTree<T>& IteratorOfVLTree<T>::OPR++( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}

if( m_p == ( *m_p ).m_right_branch ){
m_p = nullptr;

} else {
m_p = ( *m_p ).m_right_branch;
}
RET *this;
}
TMP <TYP T>
IteratorOfVLTree<T>& IteratorOfVLTree<T>::OPR--( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == ( *m_p ).m_left_branch ){
m_p = nullptr;
} else {

m_p = ( *m_p ).m_left_branch;
}
RET *this;
}
TMP <TYP T>
IteratorOfVLTree<T>& IteratorOfVLTree<T>::OPR[]( CONST_INT_REF n )
{
if( n > 0 ){

m_p = ACCESS( m_p ).m_leftmost_node;
for( int i = 1 ; i < n ; i++ ){
m_p = ACCESS( m_p ).m_right_branch;
}
} else {

if( n < 0 ){

m_p = ACCESS( m_p ).m_rightmost_node;
for( int i = -1 ; n < i ; i-- ){
	m_p = ACCESS( m_p ).m_left_branch;
}
}
}
RET *this;
}
TMP <TYP T> IteratorOfVLTree<T>& IteratorOfVLTree<T>::Shift() NEX { RET *this; }
TMP <TYP T> TMP <TYP... Args> IteratorOfVLTree<T>& IteratorOfVLTree<T>::Shift( CONST_INT_REF n , CST Args&... args ) { OPR[]( n ); RET Shift( args... ); }
TMP <TYP T> INL bool IteratorOfVLTree<T>::IsLeaf() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == ( *m_p ).m_leftmost_node ); }
TMP <TYP T> INL bool IteratorOfVLTree<T>::IsLeftMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == ( *m_p ).m_left_branch ); }
TMP <TYP T> INL bool IteratorOfVLTree<T>::IsRightMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == ( *m_p ).m_right_branch ); }
TMP <TYP T> INL bool IteratorOfVLTree<T>::IsValid() CST NEX { RET m_p != nullptr; }
// ConstIteratorOfVLTree
TMP <TYP T> INL ConstIteratorOfVLTree<T>::ConstIteratorOfVLTree() NEX : m_p( nullptr ) {}
TMP <TYP T> INL ConstIteratorOfVLTree<T>::ConstIteratorOfVLTree( CST EntryOfVLTree<T>* const& p ) NEX : m_p( p ) {}
TMP <TYP T> INL ConstIteratorOfVLTree<T>::ConstIteratorOfVLTree( CST ConstIteratorOfVLTree<T>& itr ) NEX : m_p( itr.m_p ) {}
TMP <TYP T> INL ConstIteratorOfVLTree<T>::ConstIteratorOfVLTree( CST IteratorOfVLTree<T>& itr ) NEX : m_p( itr.m_p ) {}
TMP <TYP T> INL CST T& ConstIteratorOfVLTree<T>::OPR*() CST { RET ( *m_p ).m_t; };
TMP <TYP T> INL CST T* ConstIteratorOfVLTree<T>::OPR->() CST { RET &( *( *this ) ); }
TMP <TYP T>
ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::OPR=( CST ConstIteratorOfVLTree<T>& itr ) NEX
{
m_p = itr.m_p;
RET *this;
}
TMP <TYP T>
ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::OPR=( CST IteratorOfVLTree<T>& itr ) NEX
{
m_p = itr.m_p;
RET *this;
}
TMP <TYP T>
ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::OPR++( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == ( *m_p ).m_right_branch ){
m_p = nullptr;

} else {
m_p = ( *m_p ).m_right_branch;
}
RET *this;
}
TMP <TYP T>
ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::OPR--( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == ( *m_p ).m_left_branch ){
m_p = nullptr;
} else {

m_p = ( *m_p ).m_left_branch;
}
RET *this;
}
TMP <TYP T>
ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::OPR[]( CONST_INT_REF n )
{
if( n > 0 ){

m_p = ACCESS( m_p ).m_leftmost_node;
for( int i = 1 ; i < n ; i++ ){
m_p = ACCESS( m_p ).m_right_branch;
}
}
if( n < 0 ){

m_p = ACCESS( m_p ).m_rightmost_node;
for( int i = -1 ; n < i ; i-- ){
m_p = ACCESS( m_p ).m_left_branch;
}
}
RET *this;
}
TMP <TYP T> ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::Shift() NEX { RET *this; }
TMP <TYP T> TMP <TYP... Args> ConstIteratorOfVLTree<T>& ConstIteratorOfVLTree<T>::Shift( CONST_INT_REF n , CST Args&... args ) { OPR[]( n ); RET Shift( args... ); }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::IsLeaf() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == ( *m_p ).m_leftmost_mode ); }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::IsLeftMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == ( *m_p ).m_left_branch ); }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::IsRightMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == ( *m_p ).m_right_branch ); }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::IsValid() CST NEX { RET m_p != nullptr; }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::Equal( CST IteratorOfVLTree<T>& itr0 , CST IteratorOfVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::Equal( CST ConstIteratorOfVLTree<T>& itr0 , CST IteratorOfVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::Equal( CST IteratorOfVLTree<T>& itr0 , CST ConstIteratorOfVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool ConstIteratorOfVLTree<T>::Equal( CST ConstIteratorOfVLTree<T>& itr0 , CST ConstIteratorOfVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool OPR==( CST IteratorOfVLTree<T>& itr0 , CST IteratorOfVLTree<T>& itr1 ) NEX { RET ConstIteratorOfVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IteratorOfVLTree<T>& itr0 , CST IteratorOfVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfVLTree<T>& itr0 , CST IteratorOfVLTree<T>& itr1 ) NEX { RET ConstIteratorOfVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfVLTree<T>& itr0 , CST IteratorOfVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST IteratorOfVLTree<T>& itr0 , CST ConstIteratorOfVLTree<T>& itr1 ) NEX { RET ConstIteratorOfVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IteratorOfVLTree<T>& itr0 , CST ConstIteratorOfVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST ConstIteratorOfVLTree<T>& itr0 , CST ConstIteratorOfVLTree<T>& itr1 ) NEX { RET ConstIteratorOfVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST ConstIteratorOfVLTree<T>& itr0 , CST ConstIteratorOfVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> class VLTree;
TMP <TYP T> class EntryOfUnionFindForest;
TMP <TYP T>
class VLSubTree
{
friend VLTree<T>;
friend EntryOfUnionFindForest<T>;
friend UnionFindForest<T>;

PRI:
EntryOfVLTree<T> m_e;
// 通常はm_eを指すが、VLSubTree( EntryOfVLTree<T>& )や
// VLSubTree( CST IteratorOfVLTree<T>& )経由で呼び出された場合のみ
// 参照元のNodeを指す。
EntryOfVLTree<T>* m_p_root;
uint m_size;
PRI:
// Tは引数0のコンストラクタを持つクラスのみ許容。
// デストラクタがdelete演算子を呼ばないため、VLTreeかForest経由でしか呼び出してはいけない。
INL VLSubTree();
// Tは引数0のコンストラクタを持つクラスのみ許容。
// rootのみの木に引数たちをpush_RightMostして高々m_size == 1の木を構築する。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
TMP <TYP Arg1 , TYP... Arg2> INL VLSubTree( CST Arg1& , CST Arg2&... );

// Tが引数0のコンストラクタを持たないクラスの場合に使用。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
// TMP <TYP Arg> INL VLSubTree( CST WrappedType<Arg>& t );
// 構築された木への変更がコピー元へは反映されない。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
// Substriture_Bodyを経由するため、自身への変更が引数へは反映されない。
// 引数をVLSubConstTree<T>にしたものを定義して委譲するとループしてしまう。
INL VLSubTree( CST VLSubTree<T>& );
// 構築された木への変更がコピー元へは反映される。
// VLTreeを経由しなくても呼び出して良い。
// VLTreeを経由してはならない。
INL VLSubTree( EntryOfVLTree<T>& );
INL VLSubTree( CST IteratorOfVLTree<T>& );

// 構築された木への変更がコピー元へは反映されない。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
// intはダミー引数。
INL VLSubTree( CONST_INT_REF , CST EntryOfVLTree<T>& );
INL VLSubTree( CONST_INT_REF , CST ConstIteratorOfVLTree<T>& );
// 部分木のコピーを構築してpush_RightMostNodeで挿入するため、自身への変更が引数へは反映されない。
// LeafToTreeとpush_RightMostとConcatenateの相互再帰。
// m_size == 0の時しか呼んではいけない。
void LeafToTree( CST VLSubTree<T>& );
// 新たにRightMostNodeを構築し、そこを部分木のRootとして結合する。
// 構築された木への変更がコピー元へ反映される。
// Forest経由でしか呼び出してはいけない。
void Graft( VLSubTree<T>& );

PUB:
virtual ~VLSubTree() = default;
// Substriture_Bodyを経由するため、引数が自身と独立でさえあれば、自身への変更が引数へは反映されない。
// CutBranchesを呼び出すため、引数が自身と独立でない場合は、自身への変更が引数へ反映されうる上に、Segmentation Faultを引き起こす可能性がある。
// 引数をVLTree<T>にしたものを定義して呼び出すとループしてしまう。
VLSubTree<T>& OPR=( CST VLSubTree<T>& );

INL CONST_UINT_REF size() CST NEX;
INL void CutBranches();
INL bool IsLeaf() CST NEX;
// 部分木を構築して返すため、部分木への変更が自身へも反映される。
INL VLSubTree<T> LeftMostSubTree();
INL VLSubTree<T> RightMostSubTree();

// 部分木のコピーを構築して返すため、部分木への変更が自身へは反映されない。
INL VLTree<T> LeftMostSubTreeCopy() CST;
INL VLTree<T> RightMostSubTreeCopy() CST;

// LeafToTreeとpush_RightMostとConcatenateの相互再帰。
INL void push_RightMost() CST NEX;
TMP <TYP Arg1 , TYP... Arg2> void push_RightMost( CST Arg1& , CST Arg2&... );
TMP <TYP... Args> void push_RightMost( CST VLTree<T>& , CST Args&... );
TMP <TYP Arg> void push_LeftMost( CST Arg& );

void pop_RightMost();
void pop_LeftMost();
// m_size == 1（特にm_p_root->m_leftmost_node== m_p_root->m_rightmost_node）の時しか呼んではならない。
// m_p_rootはdelete可能とは限らないため、代わりに値のすげかえを行い実際にdeleteされるのはm_p_rootでなくm_p_root->m_leftmost_nodeである。
// 従って特にiteratorの処理に注意が必要。
void pop_Root();
using iterator = IteratorOfVLTree<T>;
using const_iterator = ConstIteratorOfVLTree<T>;
// *thisがconstである場合に確実にconst_iterator返しをするために、iterator返しは非constにする必要がある。
INL iterator LeftMostNode() NEX;
INL const_iterator LeftMostNode() CST NEX;
INL iterator RightMostNode() NEX;
INL const_iterator RightMostNode() CST NEX;
iterator LeftMostLeaf() NEX;
const_iterator LeftMostLeaf() CST NEX;
iterator RightMostLeaf() NEX;
const_iterator RightMostLeaf() CST NEX;
INL iterator Root() NEX;
INL const_iterator Root() CST NEX;
TMP <TYP... Args> INL iterator GetIterator( CST Args&... );
TMP <TYP... Args> INL const_iterator GetIterator( CST Args&... ) CST;
// iteratorの右に新たなLeafを構築する。
TMP <TYP Arg> void insert( CST iterator& , CST Arg& );
// RightMostである場合はrootへのイテレータを返す。
iterator erase( iterator& );
// RootやNodeのラベルに直接読み書きを行う。
INL CST T& GetRoot() CST NEX;
INL T& RefRoot() NEX;
INL void SetRoot( CST T& );
TMP <TYP... Args> INL CST T& GetNode( CST Args&... ) CST;
// 部分木を構築して返すため、部分木への変更が自身へも反映される。
VLSubTree<T> OPR[]( CONST_UINT_REF );
VLSubTree<T> OPR[]( iterator& );

// 部分木のコピーを構築して返すため、部分木への変更が自身へは反映されない。
VLTree<T> OPR[]( CST const_iterator& ) CST;
VLTree<T> GetBranchCopy( CONST_UINT_REF ) CST;
VLTree<T> GetBranchCopy( CST iterator& ) CST;
VLTree<T> GetBranchCopy( CST const_iterator& ) CST;
// 現在のRightMostNodeやiteratorの指す位置を部分木のRootとしてコピーを構築する。
// 構築された木への変更がコピー元へは反映されない。
// LeafToTreeとpush_RightMostとConcatenateの相互再帰。
void Concatenate( CST VLTree<T>& );
void Concatenate( CST iterator& , CST VLTree<T>& );
bool CheckContain( CST iterator& ) CST NEX;
bool CheckContain( CST const_iterator& ) CST NEX;
string Display() CST;

};
TMP <TYP T> bool OPR==( CST VLTree<T>& , CST VLTree<T>& );
TMP <TYP T> INL bool OPR!=( CST VLTree<T>& , CST VLTree<T>& );
TMP <TYP T> INL VLSubTree<T>::VLSubTree() : m_e() , m_p_root( &m_e ) , m_size( 0 ) {}
TMP <TYP T> TMP <TYP Arg1 , TYP... Arg2> INL VLSubTree<T>::VLSubTree( CST Arg1& t0 , CST Arg2&... t1 ) : VLSubTree<T>() { push_RightMost( t0 , t1... ); }
// TMP <TYP T> TMP <TYP Arg> INL VLSubTree<T>::VLSubTree( CST WrappedType<Arg>& t ) : m_e( t.Get() ) , m_p_root( &m_e ) , m_size( 0 ) {}
TMP <TYP T> INL VLSubTree<T>::VLSubTree( CST VLSubTree<T>& a ) : m_e( a.m_e.m_t ) , m_p_root( &m_e ) , m_size( 0 ) { LeafToTree( a ); }
TMP <TYP T>
VLSubTree<T>::VLSubTree( EntryOfVLTree<T>& e ) :
m_e( e ) , m_p_root( &e ) , m_size( 0 )
{
EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;
if( p != m_p_root ){
m_size++;
EntryOfVLTree<T>* CST p_rightmost = m_p_root->m_rightmost_node;
while( p != p_rightmost ){
p = p->m_right_branch;
m_size++;
}

}

}
TMP <TYP T> INL VLSubTree<T>::VLSubTree( CST IteratorOfVLTree<T>& itr ) : VLSubTree( *( itr.m_p ) ) {}
TMP <TYP T>
VLSubTree<T>::VLSubTree( CONST_INT_REF dummy , CST EntryOfVLTree<T>& e ) :
m_e( e.m_t ) , m_p_root( &m_e ) , m_size( 0 )
{
CST EntryOfVLTree<T>* p = e.m_leftmost_node;
CST EntryOfVLTree<T>* CST p_rightmost = e.m_rightmost_node;
bool b = ( p != &e );
while( b ){
push_RightMost( VLTree<T>( dummy , *p ) );
b = ( p != p_rightmost );
p = p->m_right_branch;
}
}
TMP <TYP T> INL VLSubTree<T>::VLSubTree( CONST_INT_REF dummy , CST ConstIteratorOfVLTree<T>& itr ) : VLSubTree( dummy , *( itr.m_p ) ) {}
TMP <TYP T>
VLSubTree<T>& VLSubTree<T>::OPR=( CST VLSubTree<T>& a )
{
if( this != &a ){

CutBranches();
LeafToTree( a );

}
RET *this;
}
TMP <TYP T>
void VLSubTree<T>::LeafToTree( CST VLSubTree<T>& a )
{
m_p_root->m_t = a.m_p_root->m_t;
EntryOfVLTree<T>* p = a.m_p_root->m_leftmost_node;
CONST_UINT_REF N = a.m_size;

for( uint n = 0 ; n < N ; n++ ){
push_RightMost( VLTree<T>( 0 , *p ) );
p = p->m_right_branch;
}
RET;

}
TMP <TYP T> INL CONST_UINT_REF VLSubTree<T>::size() CST NEX { RET m_size; }
TMP <TYP T> INL void VLSubTree<T>::CutBranches(){ while( m_size > 0 ) pop_RightMost(); }
TMP <TYP T> INL bool VLSubTree<T>::IsLeaf() CST NEX { RET m_size == 0; }
TMP <TYP T> INL VLSubTree<T> VLSubTree<T>::LeftMostSubTree() { RET VLSubTree( *( m_p_root->m_leftmost_node ) ); }
TMP <TYP T> INL VLSubTree<T> VLSubTree<T>::RightMostSubTree() { RET VLSubTree( *( m_p_root->m_rightmost_node ) ); }
TMP <TYP T> INL VLTree<T> VLSubTree<T>::LeftMostSubTreeCopy() CST { RET VLTree<T>( 0 , *( m_p_root->m_leftmost_node ) ); }
TMP <TYP T> INL VLTree<T> VLSubTree<T>::RightMostSubTreeCopy() CST { RET VLTree<T>( 0 , *( m_p_root->m_rightmost_node ) ); }
TMP <TYP T> INL void VLSubTree<T>::push_RightMost() CST NEX {}
TMP <TYP T> TMP <TYP Arg1 , TYP... Arg2>
void VLSubTree<T>::push_RightMost( CST Arg1& t0 , CST Arg2&... t1 )
{

auto p = new EntryOfVLTree<T>( t0 );
EntryOfVLTree<T>*& p_rightmost = m_p_root->m_rightmost_node;
if( p_rightmost == m_p_root ){
m_p_root->m_leftmost_node = p;
} else {
p->m_left_branch = p_rightmost;
p_rightmost->m_right_branch = p; 
}
p_rightmost = p;
m_size++;
push_RightMost( t1... );
RET;
}
TMP <TYP T> TMP <TYP... Args>
void VLSubTree<T>::push_RightMost( CST VLTree<T>& t0 , CST Args&... t1 )
{
push_RightMost( t0.m_p_root->m_t );
Concatenate( t0 );
push_RightMost( t1... );
RET;
}
TMP <TYP T> TMP <TYP Arg>
void VLSubTree<T>::push_LeftMost( CST Arg& t )
{
auto p = new EntryOfVLTree<T>( t );
EntryOfVLTree<T>*& p_leftmost = m_p_root->m_leftmost_node;
if( p_leftmost == m_p_root ){
m_p_root->m_rightmost_node = p;
} else {
p->m_right_branch = p_leftmost;
p_leftmost->m_left_branch = p;
}

p_leftmost = p;

m_size++;
RET;
}
TMP <TYP T>
void VLSubTree<T>::pop_RightMost()
{
// if( m_size == 0 ){
// ERR_CALL;

// }

EntryOfVLTree<T>* p_rightmost = m_p_root->m_rightmost_node;
VLSubTree<T> t{ *p_rightmost };
t.CutBranches();
if( m_size == 1 ){
m_p_root->m_leftmost_node = m_p_root;
m_p_root->m_rightmost_node = m_p_root;
} else {

EntryOfVLTree<T>* const& p_rightmost_prev = p_rightmost->m_left_branch;
m_p_root->m_rightmost_node = p_rightmost_prev;
p_rightmost_prev->m_right_branch = p_rightmost_prev;
}

delete p_rightmost;
m_size--;
RET;

}
TMP <TYP T>
void VLSubTree<T>::pop_LeftMost()
{
// if( m_size == 0 ){
// ERR_CALL;

// }
EntryOfVLTree<T>* p_leftmost = m_p_root->m_leftmost_node;
VLSubTree<T> t{ *p_leftmost };
t.CutBranches();
if( m_size == 1 ){
m_p_root->m_leftmost_node = m_p_root;
m_p_root->m_rightmost_node = m_p_root;
} else {

EntryOfVLTree<T>* const& p_leftmost_next = p_leftmost->m_right_branch;
m_p_root->m_leftmost_node = p_leftmost_next;
p_leftmost_next->m_left_branch = p_leftmost_next;
}

delete p_leftmost;
m_size--;
RET;

}
TMP <TYP T>
void VLSubTree<T>::pop_Root()
{
// if( m_size != 1 ){
// ERR_CALL;

// }
EntryOfVLTree<T>* p_unique_node = m_p_root->m_leftmost_node;
m_p_root->m_t = p_unique_node->m_t;
m_p_root->m_leftmost_node = p_unique_node->m_leftmost_node;
m_p_root->m_rightmost_node = p_unique_node->m_rightmost_node;
delete p_unique_node;

EntryOfVLTree<T>* p_node = m_p_root->m_leftmost_node;
m_size = 0;
if( p_node != m_p_root ){
m_size++;

while( p_node != p_node->m_right_branch ){
p_node = p_node->m_right_branch;
m_size++;
}
}

RET;
}
TMP <TYP T> INL TYP VLSubTree<T>::iterator VLSubTree<T>::LeftMostNode() NEX { RET IteratorOfVLTree<T>( m_p_root->m_leftmost_node ); }
TMP <TYP T> INL TYP VLSubTree<T>::const_iterator VLSubTree<T>::LeftMostNode() CST NEX { RET ConstIteratorOfVLTree<T>( m_p_root->m_leftmost_node ); }
TMP <TYP T> INL TYP VLSubTree<T>::iterator VLSubTree<T>::RightMostNode() NEX { RET IteratorOfVLTree<T>( m_p_root->m_rightmost_node ); }
TMP <TYP T> INL TYP VLSubTree<T>::const_iterator VLSubTree<T>::RightMostNode() CST NEX { RET ConstIteratorOfVLTree<T>( m_p_root->m_rightmost_node ); }
TMP <TYP T>
TYP VLSubTree<T>::iterator VLSubTree<T>::LeftMostLeaf() NEX
{
EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;
while( p != p->m_leftmost_node ){
p = p->m_leftmost_node;
}
RET IteratorOfVLTree<T>( p );
}
TMP <TYP T>
TYP VLSubTree<T>::const_iterator VLSubTree<T>::LeftMostLeaf() CST NEX
{
CST EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;
while( p != p->m_leftmost_node ){
p = p->m_leftmost_node;
}
RET ConstIteratorOfVLTree<T>( p );
}
TMP <TYP T>
TYP VLSubTree<T>::iterator VLSubTree<T>::RightMostLeaf() NEX
{
EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;
while( p != p->m_rightmost_node ){
p = p->m_rightmost_node;
}
RET IteratorOfVLTree<T>( p );
}
TMP <TYP T>
TYP VLSubTree<T>::const_iterator VLSubTree<T>::RightMostLeaf() CST NEX
{
CST EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;
while( p != p->m_rightmost_node ){
p = p->m_rightmost_node;
}
RET ConstIteratorOfVLTree<T>( p );
}
TMP <TYP T> INL TYP VLSubTree<T>::iterator VLSubTree<T>::Root() NEX { RET IteratorOfVLTree<T>( m_p_root ); }
TMP <TYP T> INL TYP VLSubTree<T>::const_iterator VLSubTree<T>::Root() CST NEX { RET ConstIteratorOfVLTree<T>( m_p_root ); }
TMP <TYP T> TMP <TYP... Args> INL TYP VLSubTree<T>::iterator VLSubTree<T>::GetIterator( CST Args&... args ) { RET Root().Shift( args... ); }
TMP <TYP T> TMP <TYP... Args> INL TYP VLSubTree<T>::const_iterator VLSubTree<T>::GetIterator( CST Args&... args ) CST { RET Root().Shift( args... ); }
TMP <TYP T> TMP <TYP Arg>
void VLSubTree<T>::insert( CST TYP VLSubTree<T>::iterator& itr , CST Arg& t )
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr , t );

// }

EntryOfVLTree<T>* const& p0 = itr.m_p;
EntryOfVLTree<T>* const& p1 = p0->m_right_branch;
auto p = new EntryOfVLTree<T>( t , p0 , p1 );

p1->m_left_branch = p;
p0->m_right_branch = p;

m_size++;
RET;
}
TMP <TYP T>
TYP VLSubTree<T>::iterator VLSubTree<T>::erase( TYP VLSubTree<T>::iterator& itr )
{

// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr );

// }
EntryOfVLTree<T>* CST p = itr.m_p;
EntryOfVLTree<T>* CST p0 = p->m_left_branch;
EntryOfVLTree<T>* CST p1 = p->m_right_branch;
if( ! itr.IsLeaf() ){
VLSubTree<T> t_sub{ *p };
t_sub.CutBranches();

}

if( p0 != p ){
if( p != p1 ){
itr++;
p0->m_right_branch = p1;
p1->m_left_branch = p0;

} else {
itr--;
p0->m_right_branch = p0;
m_p_root->m_rightmost_node = p0;
}
} else {
if( p != p1 ){
itr++;
p1->m_left_branch = p1;
m_p_root->m_leftmost_node = p1;
} else {
itr = Root();
m_p_root->m_leftmost_node = m_p_root;
m_p_root->m_rightmost_node = m_p_root;
}
}

delete p;
m_size--;
RET itr;
}
TMP <TYP T> INL CST T& VLSubTree<T>::GetRoot() CST NEX { RET m_p_root->m_t; }
TMP <TYP T> INL T& VLSubTree<T>::RefRoot() NEX { RET m_p_root->m_t; }
TMP <TYP T> INL void VLSubTree<T>::SetRoot( CST T& t ){ m_p_root->m_t = t; }
TMP <TYP T> TMP <TYP... Args> INL CST T& VLSubTree<T>::GetNode( CST Args&... args ) CST { RET ACCESS( GetIterator( args... ) ); }
TMP <TYP T>
VLSubTree<T> VLSubTree<T>::OPR[]( CONST_UINT_REF i )
{
// if( i >= m_size ){
// ERR_IMPUT( i );
// }
if( i <= m_size / 2 ){
EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;
for( uint n = 0 ; n < i ; n++ ){
p = p->m_right_branch;
}
RET VLSubTree<T>( *p );
}
EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;
for( uint n = m_size - 1 ; n > i ; n-- ){
p = p->m_left_branch;
}
RET VLSubTree<T>( *p );
}
TMP <TYP T>
VLSubTree<T> VLSubTree<T>::OPR[]( TYP VLSubTree<T>::iterator& itr )
{
// if( ! CheckContain( itr )){
// ERR_IMPUT( itr );
// }
RET VLSubTree<T>( *( itr.m_p ) );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::OPR[]( CST TYP VLSubTree<T>::const_iterator& itr ) const
{
// if( ! CheckContain( itr )){
// ERR_IMPUT( itr );
// }
RET VLTree<T>( 0 , itr.m_p );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::GetBranchCopy( CONST_UINT_REF i ) const
{
// if( i >= m_size ){
// ERR_IMPUT( i );
// }
if( i <= m_size / 2 ){
CST EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;
for( uint n = 0 ; n < i ; n++ ){
p = p->m_right_branch;
}
RET VLTree<T>( 0 , *p );
}
CST EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;
for( uint n = m_size - 1 ; n > i ; n-- ){
p = p->m_left_branch;
}
RET VLTree<T>( 0 , *p );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::GetBranchCopy( CST TYP VLSubTree<T>::iterator& itr ) const
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr );
// }
RET VLTree<T>( 0 , *( itr.m_p ) );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::GetBranchCopy( CST TYP VLSubTree<T>::const_iterator& itr ) const
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr );
// }
RET VLTree<T>( 0 , *( itr.m_p ) );
}
TMP <TYP T> 
void VLSubTree<T>::Concatenate( CST VLTree<T>& t )
{
EntryOfVLTree<T>* CST p_rightmost = m_p_root->m_rightmost_node;
// if( p_rightmost->m_rightmost_node != p_rightmost ){
// ERR_IMPUT( *this , t );
// }
if( m_p_root == p_rightmost ){

LeafToTree( t );
} else {
VLSubTree<T>( *p_rightmost ).LeafToTree( t );
}

RET;
}
TMP <TYP T> 
void VLSubTree<T>::Concatenate( CST TYP VLSubTree<T>::iterator& itr , CST VLTree<T>& t )
{
// if( ! itr.IsLeaf() ){
// ERR_IMPUT( itr , t );
// }

EntryOfVLTree<T>* CST p = itr.m_p;
if( m_p_root == p ){
LeafToTree( t );
} else {
VLSubTree<T>( *p ).LeafToTree( t );
}

RET;
}
TMP <TYP T> 
void VLSubTree<T>::Graft( VLSubTree<T>& t )
{
EntryOfVLTree<T>*& p_rightmost = m_p_root->m_rightmost_node;
// if( p_rightmost->m_rightmost_node != p_rightmost ){
// ERR_IMPUT( *this , t );
// }
if( m_p_root == p_rightmost ){

p_rightmost = m_p_root->m_leftmost_node = t.m_p_root;
} else {
p_rightmost = p_rightmost->m_right_branch = t.m_p_root;
}

RET;
}
TMP <TYP T>
bool VLSubTree<T>::CheckContain( CST iterator& itr ) CST NEX
{
auto p0 = itr.m_p;
auto p1 = m_p_root->m_leftmost_node;

for( uint i = 0 ; i < m_size ; i++ ){
if( p0 == p1 ){
RET true;
}
p1 = p1->m_right_branch;

}
RET false;
}
TMP <TYP T>
bool VLSubTree<T>::CheckContain( CST const_iterator& itr ) CST NEX
{
auto p0 = itr.m_p;
auto p1 = m_p_root->m_leftmost_node;

for( uint i = 0 ; i < m_size ; i++ ){
if( p0 == p1 ){
RET true;
}
p1 = p1->m_right_branch;

}
RET false;
}
TMP <TYP T>
string VLSubTree<T>::Display() const
{

string s = to_string( m_p_root->m_t );
s += "(";

CST EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;

for( uint i = 0 ; i < m_size ; i++ ){
if( i > 0 ){
s += ",";
}

s += VLTree<T>( 0 , *p ).Display();

p = p->m_right_branch;
}
s += ")";
RET s;
}
TMP <TYP T>
bool OPR==( CST VLTree<T>& t1 , CST VLTree<T>& t2 )
{
if( t1.GetRoot() != t2.GetRoot() ){
RET false;
}

if( t1.IsLeaf() ){
RET t2.IsLeaf();
}
if( t2.IsLeaf() ){
RET false;
}
auto itr1 = t1.LeftMostNode();
auto itr2 = t2.LeftMostNode();
while( itr1.IsValid() && itr2.IsValid() ){
if( t1.GetBranchCopy( *itr1 ) != t2.GetBranchCopy( *itr2 ) ){
RET false;
}
itr1++;
itr2++;
}
RET !( itr1.IsValid() || itr2.IsValid() );
}
TMP <TYP T> INL bool OPR!=( CST VLTree<T>& t1 , CST VLTree<T>& t2 ) { RET !( t1 == t2 ); }
TMP <TYP T>
class VLTree :
PUB VLSubTree<T>
{
PUB:
TMP <TYP... Args> INL VLTree( CST Args&... );
VLTree( EntryOfVLTree<T>& ) = delete;
virtual ~VLTree();
TMP <TYP Arg> VLTree<T>& OPR=( CST Arg& );
};
TMP <TYP T> TMP <TYP... Args> INL VLTree<T>::VLTree( CST Args&... t ) : VLSubTree<T>( t... ) {}
TMP <TYP T> VLTree<T>::~VLTree(){ VLSubTree<T>::CutBranches(); }
TMP <TYP T> TMP <TYP Arg>
VLTree<T>& VLTree<T>::OPR=( CST Arg& t )
{
VLSubTree<T>::OPR=( t );
RET *this;
}
TMP <TYP T> class UnionFindForest;
TMP <TYP T> class EntryOfLinkedVector;
TMP <TYP T>
class EntryOfUnionFindForest
{
friend UnionFindForest<T>;
friend EntryOfLinkedVector<EntryOfUnionFindForest<T> >;

PRI:
VLSubTree<T> m_node;
uint m_pred_node;
uint m_root;
uint m_depth;
PRI:
INL EntryOfUnionFindForest();
INL EntryOfUnionFindForest( CST T& t , CONST_UINT_REF num );
INL EntryOfUnionFindForest( EntryOfUnionFindForest&& e );
};
TMP <TYP T> INL EntryOfUnionFindForest<T>::EntryOfUnionFindForest() : m_node() , m_pred_node( 0 ) , m_root( 0 ) , m_depth( 0 ) {}
TMP <TYP T> INL EntryOfUnionFindForest<T>::EntryOfUnionFindForest( CST T& t , CONST_UINT_REF num ) : m_node() , m_pred_node( num ) , m_root( num ) , m_depth( 0 ) { m_node.SetRoot( t ); }
TMP <TYP T> INL EntryOfUnionFindForest<T>::EntryOfUnionFindForest( EntryOfUnionFindForest<T>&& e ) : m_node() , m_pred_node( move( e.m_pred_node ) ) , m_root( move( e.m_root ) ) , m_depth( move( e.m_depth ) ) { m_node.SetRoot( move( e.m_node.m_p_root->m_t ) ); }
TMP <TYP T>
class UnionFindForest :
PUB LinkedVector<EntryOfUnionFindForest<T> >
{
PUB:
// EntryOfUnionFindForest<T>::m_nodeはVLSubTree<T>型でありポインタをメンバに持つため
// 予め最大要素数を固定しないといけない。
INL UnionFindForest( CONST_UINT_REF max_size );
// num番目のNodeをRootとする部分木を構築する。
INL CST VLSubTree<T>& GetSubTree( CONST_UINT_REF num ) CST;
// num番目のNodeのPredecessor Nodeを返す。
INL CONST_UINT_REF GetPredecessorNode( CONST_UINT_REF num ) CST;
// num番目のNodeのRootを計算して返す。
CONST_UINT_REF GetRootOfNode( CONST_UINT_REF num );
// num番目のRootを返す。
uint GetRoot( CONST_UINT_REF num ) CST;
// num番目のNodeに格納された値への参照を返す。
INL CST T& OPR[]( CST uint& num ) CST;
INL T& OPR[]( CST uint& num );

INL CONST_UINT_REF GetSizeOfNode() CST NEX;
INL CONST_UINT_REF GetSizeOfRoot() CST NEX;
// 最初に指定したmax_sizeよりGetSizeOfNode()が大きい場合はサポート外
INL void push_RightMost();
void push_RightMost( CST T& t );
TMP <TYP... ARGS> INL void push_RightMost( CST T& t , CST ARGS&... args );
INL void push_back() = delete;
TMP <TYP U> void push_back( CST U& u ) = delete;
TMP <TYP U , TYP... ARGS> INL void push_back( CST U& u , CST ARGS&... args ) = delete;
INL void SetPreviousLink( CONST_UINT_REF i , CONST_UINT_REF j ) = delete;
INL void SetNexttLink( CONST_UINT_REF i , CONST_UINT_REF j ) = delete;
INL CONST_UINT_REF GetPreviousLinkIndex( CONST_UINT_REF i ) CST = delete;
INL CONST_UINT_REF GetNexttLinkIndex( CONST_UINT_REF i ) CST = delete;
CONST_UINT_REF DeLink( CONST_UINT_REF i ) = delete;
void ReLink( CONST_UINT_REF i ) = delete;

void Graft( CONST_UINT_REF num0 , CONST_UINT_REF num1 );

};
TMP <TYP T> INL UnionFindForest<T>::UnionFindForest( CONST_UINT_REF max_size ) : LinkedVector<EntryOfUnionFindForest<T> >( max_size ) {}
TMP <TYP T> INL CST VLSubTree<T>& UnionFindForest<T>::GetSubTree( CONST_UINT_REF num ) CST { RET LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num ).m_node; }
TMP <TYP T> INL CONST_UINT_REF UnionFindForest<T>::GetPredecessorNode( CONST_UINT_REF num ) CST { RET LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num ).m_pred_node; }
TMP <TYP T>
CONST_UINT_REF UnionFindForest<T>::GetRootOfNode( CONST_UINT_REF num )
{
uint& root = LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num ).m_root;
if( root != LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( root ).m_root ){
root = GetRootOfNode( root );

}
RET root;
}
TMP <TYP T>
uint UnionFindForest<T>::GetRoot( CONST_UINT_REF num ) const
{
auto itr = LinkedVector<EntryOfUnionFindForest<T> >::begin();
for( uint i = 0 ; i < num ; i++ ){
itr++;
}
RET itr.GetIndex();

}
TMP <TYP T> INL CST T& UnionFindForest<T>::OPR[]( CST uint& num ) CST { RET LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num ).m_node.GetRoot(); }
TMP <TYP T> INL T& UnionFindForest<T>::OPR[]( CST uint& num ) { RET LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num ).m_node.RefRoot(); }
TMP <TYP T> INL CONST_UINT_REF UnionFindForest<T>::GetSizeOfNode() CST NEX { RET LinkedVector<EntryOfUnionFindForest<T> >::GetSizeOfVector(); }
TMP <TYP T> INL CONST_UINT_REF UnionFindForest<T>::GetSizeOfRoot() CST NEX { RET LinkedVector<EntryOfUnionFindForest<T> >::GetSizeOfLink(); }
TMP <TYP T> INL void UnionFindForest<T>::push_RightMost() {}
TMP <TYP T>
void UnionFindForest<T>::push_RightMost( CST T& t )
{
EntryOfLinkedVector<EntryOfUnionFindForest<T> >& e = LinkedVector<EntryOfUnionFindForest<T> >::push_back_Body_0();
e.m_t.m_node.SetRoot( t );
e.m_t.m_pred_node = e.m_t.m_root = LinkedVector<EntryOfUnionFindForest<T> >::m_size_of_vector;
LinkedVector<EntryOfUnionFindForest<T> >::push_back_Body_1( e );
RET;
}
TMP <TYP T> TMP <TYP... ARGS> INL void UnionFindForest<T>::push_RightMost( CST T& t , CST ARGS&... args ) { push_RightMost( t ); push_RightMost( args... ); }
TMP <TYP T>
void UnionFindForest<T>::Graft( CONST_UINT_REF num0 , CONST_UINT_REF num1 )
{
CONST_UINT_REF e0_root_index = LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num0 ).m_root;
CONST_UINT_REF e1_root_index = LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( num1 ).m_root;
if( e0_root_index == e1_root_index ){
RET;

}
EntryOfUnionFindForest<T>& e0_root = LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( e0_root_index );
EntryOfUnionFindForest<T>& e1_root = LinkedVector<EntryOfUnionFindForest<T> >::OPR[]( e1_root_index );
CST uint i0 = ( e0_root.m_depth < e1_root.m_depth ? 0 : 1 );
CST uint i1 = 1 - i0;
EntryOfUnionFindForest<T>* CST p_e_root[2] = { &e0_root , &e1_root };
EntryOfUnionFindForest<T>& root_0 = *( p_e_root[i0] );
EntryOfUnionFindForest<T>& root_1 = *( p_e_root[i1] );
if( root_0.m_depth == root_1.m_depth ){
root_1.m_depth++;
}
root_1.m_node.Graft( root_0.m_node );
LinkedVector<EntryOfUnionFindForest<T> >::DeLink( root_0.m_root );
root_0.m_root = root_0.m_pred_node = root_1.m_root;
RET;
}
int main()
{
UNTIE;
constexpr CST uint bound = 200001;
CIN( uint , N );
assert( N < bound );
UnionFindForest<int> f{ N };
FOR( i , 0 , N ){
f.push_RightMost( 0 );
}
CIN( uint , M );
assert( M < bound );
int u[bound];
int v[bound];
int uvj;
FOR( j , 0 , M ){
cin >> uvj;
uvj--;
u[j] = uvj;
cin >> uvj;
uvj--;
v[j] = uvj;
}
while( M-- != 0 ){
CONST_INT_REF uj = u[M];
CONST_INT_REF vj = v[M];
CONST_UINT_REF uj_root = f.GetRootOfNode( uj );
CONST_UINT_REF vj_root = f.GetRootOfNode( vj );
int& count_0 = f[uj_root];
int& count_1 = f[vj_root];
if( count_0 < count_1 ){
count_0 = ++count_1;
} else {
count_1 = ++count_0;
}
f.Graft( uj_root , vj_root );
}
RETURN( f[ f.GetRootOfNode( 0 ) ] );
}
yukicoder

結果

テストケース

ソースコード
