Yes, as long as the vector has been sorted using the Boolean operator<.

Example:

struct mystruct: public pair< int, int > {

    mystruct( const int x, const int y ) { first = x, second = y; }

    bool operator < ( const mystruct &b ) const { return first < b.first || ( first == b.fist && second < b.second); }

    friend ostream& operator << ( ostream &os, const mystruct &b ) { return os << b.first << " " << b.second; }
};

int main()
{
    vector< mystruct > z;

    z.emplace_back( 3, 4 );
    z.emplace_back( 1, 2 );
    z.emplace_back( 5, 6 );

    sort( z.begin(), z.end() );

    for( auto x: z )
        cout << x << endl;

    cout << endl;

    cout << *lower_bound( z.begin(), z.end(), mystruct( 3, 3 ) ) << endl;

    cout << *upper_bound( z.begin(), z.end(), mystruct( 4, 4 ) ) << endl;
}

Output:

1 2

3 4

5 6

3 4

5 6

The following is the previous example augmented with struct myvector wrapper for vector< mystruct >:

struct mystruct: public pair< int, int > {

    mystruct( const int x, const int y ) { first = x, second = y; }

    bool operator < ( const mystruct &a ) const { return first < a.first || ( first == a.first && second < a.second ); }

    friend ostream& operator << ( ostream &os, const mystruct &a ) { return os << x.first << " " << x.second; }
};

struct myvector: public vector< mystruct >
{

    void order() { sort( begin(), end() ); }

    friend ostream& operator << ( ostream& os, const myvector &v )
    {
        for( auto x: v )
            os << x << endl;

        return os;
    }

    iterator lb( const mystruct &x ) { return lower_bound( begin(), end(), x ); }

    iterator ub( const mystruct &x ) { return upper_bound( begin(), end(), x ); }

} z;

int main()
{
    z.emplace_back( 3, 4 );
    z.emplace_back( 1, 2 );
    z.emplace_back( 5, 6 );

    z.order();

    cout << z << endl;

    cout << *z.lb( mystruct( 3, 3 ) ) << endl;

    cout << *z.ub( mystruct( 4, 4 ) ) << endl;
}

Thanks for the clarification.

In the statement of the aforementioned problem, it is guaranteed that no two rectangle boundaries intersect.

The solution uses a rectangle_tree class whose root node is the entire 2500 x 2500 area. The children of each node (u) in the rectangle_tree are the largest non-intersecting rectangles contained in (u). Insertions and deletions update the tree according to inserted/deleted rectangles. A walk query returns "Yes" if and only if the smallest rectangles containing the source and the target cells are the same.

The Boolean operator are used to compare the corresponding upper-left and lower-right of rectangle pairs preserving the order of the corner cells, and to compare query points to those corner cells. Therefore, there is on luck in the success of the solution.

It is just the case that those counterexamples mentioned in your clarification are guaranteed to never take place.

The Boolean operator< is NOT used to sort an array of 2D points. It is just used to update the rectangle tree when a rectangle is inserted or deleted.

Best Regards.