問題としては情報は全部出てるな．これで分からないのは理解する気が無いんだろ．

長方形が一つだけ与えられてその中から探すのなら，
データの前のほうから包含チェックが最速．O(n)．

長方形がたくさん与えられて，各入力に対して答えるのなら
データをフラクショナルカスケーディング付きの領域木に入れておく．
これで構成 O(n log n)，質問 O(log n + k)．ただし k は領域内の点の数．