CFR Educational 10 D. Nested Segments ( Segment Tree + Scanning Line )

Problem - D - Codeforces
Sort by left bound, that scan from left to right, we will query the number of right bounds that are before the right bound of the current segment. After answering the query, the segment should be removed, which will have us delete its right bound. Making good use of sorting and scanning line, we can suppress the complexity efficiently.

void solve(){
    for(int i = 0; i < n; ++i){
        root->update( r[ lsrtd[ i ].Y ], -1 );
        ans[ lsrtd[ i ].Y ] += root->qsum( root->lb, r[ lsrtd[ i ].Y ] );
    }
    for(int i = 0; i < n; ++i)
        printf("%d\n", ans[ i ]);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", l + i, r + i);
    root = new itvt( *min_element( r, r + n ), *max_element( r, r + n ) );
    for(int i = 0; i < n; ++i)
        root->update( r[ i ], 1 );
    for(int i = 0; i < n; ++i)
        lsrtd.push_back( pii( l[ i ], i ) );
    sort( lsrtd.begin(), lsrtd.end() );
    solve();
    return 0;
}