CFR 276 D. Little Girl and Maximum XOR ( Digit XOR DP )

Problem - 276D - Codeforces

題意：
給 L, R，求任一對 A, B，滿足 L ≤ A ≤ B ≤ R，可得的最大 A XOR B。

數據範圍：
1 ≤ L ≤ R ≤ 1e18

解法：
先將 L，R 轉換為二進制，若長度有差則補零在前頭。接著在這上面做動態規劃( 數位統計 )。
dp[ i ][ j ][ k ][ l ][ m ] : 已考慮前 i 個 bit，L 確定會 < A，A 確定會 < R，L 確定 < B，B 確定 < R，且確定 L ≤ A ≤ B ≤ R，此時的最大 A XOR B
狀態轉移很顯然，詳見代碼。

時間 / 空間複雜度：
O( lg( R ) )

需要注意：
因為 dp值初始為 0，而不是負無窮那類，因此會讓一些不能轉移的狀態發生轉移。因此要另外開一個 vis 陪著，當且僅當被更新過的 dp值才可以拿來更新其他狀態。
除錯花了很多時間才發現，原來 ? : 比 < 順序低。。。

ll L, R;

void init(){
    cin >> L >> R;
}

vi bl, br; // binary l, binary r
vvvvvl dp;
vvvvvi vis;

void preprocess(){
    for( ll l = L; l; l /= 2 )
        bl.emplace_back( l % 2 );
    for( ll r = R; r; r /= 2 )
        br.emplace_back( r % 2 );
    while( bl.size() < br.size() )
        bl.emplace_back( 0 );
    reverse( bl.begin(), bl.end() );
    reverse( br.begin(), br.end() );
    dp = vvvvvl( bl.size() + 1, vvvvl( 2, vvvl( 2, vvl( 2, vl( 2 ) ) ) ) );
    vis = vvvvvi( bl.size() + 1, vvvvi( 2, vvvi( 2, vvi( 2, vi( 2 ) ) ) ) );
    vis[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ] = 1;
    for( int i = 0; i < bl.size(); ++i )
        for( int j = 0; j < 2; ++j ) // >
            for( int k = 0; k < 2; ++k ) // <
                for( int l = 0; l < 2; ++l ) // >
                    for( int m = 0; m < 2; ++m ) if( vis[ i ][ j ][ k ][ l ][ m ] )// < 
                        for( int d1 = ( j ? 0 : bl[ i ] ); d1 <= ( k ? 1 : br[ i ] ); ++d1 )
                            for( int d2 = ( l ? 0 : bl[ i ] ); d2 <= ( m ? 1 : br[ i ] ); ++d2 )
                                upmax( dp[ i + 1 ][ j | d1 > bl[ i ] ][ k | d1 < br[ i ] ][ l | d2 > bl[ i ] ][ m | d2 < br[ i ] ],
                                       dp[ i ][ j ][ k ][ l ][ m ] * 2 + ( d1 ^ d2 ) ),
                                vis[ i + 1 ][ j | d1 > bl[ i ] ][ k | d1 < br[ i ] ][ l | d2 > bl[ i ] ][ m | d2 < br[ i ] ] = 1;
}

void solve(){
    ll ans = 0;
    for( int i = 0; i < 2; ++i )
        for( int j = 0; j < 2; ++j )
            for( int k = 0; k < 2; ++k )
                for( int l = 0; l < 2; ++l )
                    upmax( ans, dp[ bl.size() ][ i ][ j ][ k ][ l ] );
    cout << ans << endl;
}