CFR 689 D. Friends and Subsequences ( Binary Search + Sparse Table RMQ )

Problem - D - Codeforces
When there are functions, try to find the monotonic property.
Both max function and mix function have monotonic property, for the former is non-decreasing and the latter is non-increasing. We are interested of the difference between the two functions when ranges are fixed. The function of the difference, which let us define f( l, r ) = a_max( l, r ) - b_min( l, r ), is again non-decreasing. We are willing to find the count of ( l, r ) where f( l, r ) = 0. If we fix for a certain l, we are to find the position of the minimal r and that of the maximal r, where f( l, r ) = 0. As said before f() is a monotonic function, so we can apply binary search to find the r. I implemented two different binary searches, one to find the leftmost, and the other to find the rightmost. Of course, the RMQ will be dealt with sparse table, which holds constant time complexity for each query. Thus, the time complexity is O( n lg n ).

const int MAXN = 2e5 + 5;

int N;
int A[ MAXN ];
int B[ MAXN ];

int amaxst[ MAXN ][ 20 ];
int bminst[ MAXN ][ 20 ];

int qmax( int st[][ 20 ], int ql, int qr ){
    int k = 31 - __builtin_clz( qr - ql + 1 );
    return max( st[ ql ][ k ], st[ qr - ( 1 << k ) + 1 ][ k ] );
}

int qmin( int st[][ 20 ], int ql, int qr ){
    int k = 31 - __builtin_clz( qr - ql + 1 );
    return min( st[ ql ][ k ], st[ qr - ( 1 << k ) + 1 ][ k ] );
}

int get_diff( int ql, int qr ){ // get a_max[ ql, qr ] - b_min[ ql, qr ]
    int a_max = qmax( amaxst, ql, qr );
    int b_min = qmin( bminst, ql, qr );
    return a_max - b_min;
}

int get_min_idx( int lb ){ // get minimum rb such that [ lb, rb ] is countable
    int x = lb, y = N - 1;
    int res = -1;
    while( x <= y ){
        int mid = x + y >> 1;
        int d = get_diff( lb, mid );
        if( d == 0 ) res = mid, y = mid - 1;
        else if( d > 0 ) y = mid - 1;
        else x = mid + 1;
    }
    return res;
}

int get_max_idx( int lb ){ // get maximum rb such that [ lb, rb ] is countable
    int x = lb, y = N - 1;
    int res = -1;
    while( x <= y ){
        int mid = x + y >> 1;
        int d = get_diff( lb, mid );
        if( d == 0 ) res = mid, x = mid + 1;
        else if( d > 0 ) y = mid - 1;
        else x = mid + 1;
    }
    return res;
}

void solve(){
    cin >> N;
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    for( int i = 0; i < N; ++i )
        cin >> B[ i ];

    for( int i = 0; i < N; ++i )
        amaxst[ i ][ 0 ] = A[ i ],
        bminst[ i ][ 0 ] = B[ i ];
    for( int k = 0; k + 1 < 20; ++k )
        for( int i = 0; i < N; ++i ) if( i + ( 1 << k + 1 ) <= N ){
            int m = i + ( 1 << k );
            amaxst[ i ][ k + 1 ] = max( amaxst[ i ][ k ], amaxst[ m ][ k ] );
            bminst[ i ][ k + 1 ] = min( bminst[ i ][ k ], bminst[ m ][ k ] );
        }

    ll ans = 0;
    for( int lb = 0; lb < N; ++lb ){
        int minrb = get_min_idx( lb );
        int maxrb = get_max_idx( lb );
        if( minrb == -1 or maxrb == -1 ){
            assert( minrb == maxrb );
            continue;
        }
        ans += maxrb - minrb + 1;
    }

    cout << ans << "\n";
}