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

Problem - 276D - Codeforces

1 ≤ L ≤ R ≤ 1e18

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 ) )

```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;
}
```