これは宿題の問題ではありません。インタビューの質問です。この問題の良い解決策が思いつきません。
問題 ：
n*n (左下(0,0) 、右上(n,n)) グリッドと、座標軸に平行な辺を持つ n 個の長方形が与えられます。n 個の長方形の左下と右上の座標は、(x1,y1)(x1',y1') .... (xn,yn)(xn',yn') の形式で提供されます。座標 (a,b)(c,d) の長方形を覆う長方形の数を求めるクエリが M 個あります。効率的な方法でそれを解決するにはどうすればよいですか? O(1) で答えを返すことができるように、すべての座標位置を事前計算する方法はありますか?
制約: 1<= n <= 1000
O(n^4) 空間と O(n^5) 時間で、O(1) ルックアップを提供するデータ構造を作成するのは簡単です。M が O(n^2) を超える場合は、そうする価値があるかもしれません。また、O(n^2) 空間と O(n^3) 時間で、O(n) 時間でルックアップを提供するデータ構造を簡単に作成できます。M が O(n^2) の場合は、より良いトレードオフになる可能性があります。つまり、O(n) ごとに O(n^2) 回のルックアップに O(n^3) の事前計算時間と O(n^3) の時間がかかります。
事前計算のために、リストの n 行 n 列の配列を作成します。L_pq は、n x n グリッドのセル p,q のリストを示します。各リストには最大 n 個の長方形が含まれ、リストはすべて同じ関係で並べられます (つまりRi < Rj、1 つのリスト内にある場合はRi < Rj、そのペアが含まれるすべてのリスト内)。リストのセットの計算には O(n^3) の時間がかかり、「n^2 セルの各 C に対して、n 四角形の各 R に対して、R の C が R を L_C に追加する場合」または「各 R に対して」のいずれかとして取得されます。 R の各セル C について、R を L_C に追加します。
クエリ (a、b、c、d) が与えられると、O(n) で、リスト L_ab と L_cd の共通部分のサイズがカウントされます。O(1) ルックアップの場合、最初に上記の事前計算を行い、次に各 a、b、および ごとc>aにd<b、上記の O(n) クエリを実行し、結果を P[a,b,c,d] に保存します。ここで、P は適切に大きな整数の配列です。
O(n^3) またはおそらく O(n^2 · log n) の事前計算方法は、O(log n) 時間でクエリを実行できるセグメント ツリー、レンジ ツリー、またはインターバル ツリーのいずれかを使用して存在する可能性があります。