// #define _GLIBCXX_DEBUG #include 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( ll 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 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; template inline T Absolute( const T& a ){ return a > 0 ? a : - a; } // 以下、自分のライブラリ(https://github.com/p-adic/cpp)よりソースコードをコピーして編集している。 class seq { public: ll m_n; ll m_i; inline seq() : m_n() , m_i() {} inline seq( const ll& n , const ll& i ) : m_n( n ) , m_i( i ) {} }; class ord { public: inline bool operator()( const seq& N0 , const seq& N1 ) { return N0.m_n < N1.m_n; } }; inline ll f( const ll& n ) { return n == 0 ? 0 : n % 2 == 0 ? f( n / 2 ) : f( ( n + 1 ) / 4 ) + 1; } // ( ( max - 1 ) / 4 - ( start + 2 ) / 4 + 1 ) + ( max + 1 ) / 4 - ( start / 4 + 1 + 1 ) // = ( ( max - 1 ) / 4 + ( max + 1 ) / 4 ) - ( ( start + 2 ) / 4 + start / 4 ) + 1 // = ( max + 1 ) / 2 - start / 2 inline ll sum_f( const ll& start , const ll& max ) { return start > max ? 0 : start == max ? f( start ) : sum_f( ( start + 1 ) / 2 , max / 2 ) + sum_f( ( start + 2 ) / 4 , start / 4 ) + sum_f( start / 4 + 1 , ( max - 1 ) / 4 ) * 2 + sum_f( ( max + 3 ) / 4 , ( max + 1 ) / 4 ) + ( max + 1 ) / 2 - start / 2; } int main() { UNTIE; CIN( ll , T ); seq N[10000]; FOR( i , 0 , T ){ seq& Ni = N[i]; cin >> Ni.m_n; Ni.m_i = i; } sort( N , N + T , ord() ); ll answer[10000]; ll* p_N_prev; ll* p_answer_prev; { seq& Ni = N[0]; ll& answer_new = answer[ Ni.m_i ]; answer_new = sum_f( 1 , Ni.m_n ); p_N_prev = &( Ni.m_n ); p_answer_prev = &( answer_new ); } FOR( i , 1 , T ){ seq& Ni = N[i]; ll& answer_new = answer[ Ni.m_i ]; answer_new = *p_answer_prev + sum_f( *p_N_prev + 1 , Ni.m_n ); p_N_prev = &( Ni.m_n ); p_answer_prev = &( answer_new ); } FOR( i , 0 , T ){ cout << answer[i] << "\n"; } return 0; }