Given a list containing N (1 <= N <= 10 ^ 5) rectangles and Q (1 <= Q <= 10 ^ 5) queries. The i-th query will give a point (u, v). I need to print the index of the smallest rectangle in the list that encloses that point.
A rectangle is defined as two points (x1, y1) at the bottom left and (x2, y2) at the top right.
x1, y1, x2, y2 are odd numbers.
There are no two rectangles intersect with each other
u, v are even numbers
All coordinates in the input are integers from 1 to 5000, inclusive.
If the statement isn’t clear enough, please tell me.
There are no two rectangles intersect with each other
There will be at most one rectangle enclosing any point, take a 2D array of size 5000*5000, and for each rectangle mark all points in it in the array with its area. When you query for a point, print the value in that position.
Thank you so much!
This is not a part of the question, just more advance.
If I have a second type of query that will remove any rectangle.
More formally, in 10^5 queries will now include a second type of query that will erase some of the rectangles in the given list and we have to give out a new smallest rectangle index for a same point.
There is a simple offline solution for that. Read all queries and process in reverse order. Start with only rectangles that were not part of any delete query. Now delete becomes add ie. you have 2 types of queries, add a rectangle, find which rectangle contains a point. You can do it in the same way, fill the squares whenever you add a rectangle, and look up for points. You can use a 2D binary indexed tree if you want an online solution.